[프로그래머스]Lv2.달리기 경주 달리기 경주(Java)

프로그래머스 달리기 경주 자바로 풀기

먼저 문제를 간단하게 설명하고 알고리즘으로 접근 하겠습니다!

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

정답

 

 

 

---

문제 설명

해설진들은 자기 앞의 선수를 추월할 때마다 추월한 선수의 이름을 부릅니다.

한명을 추월했을 때는 추월한 선수의 이름 한번,

두명을 추월했을 떄는 추월한 선수의 이름 두번을 부릅니다.

 

예를 들어,

1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 

해설진이 "soe" 선수의 이름을 부르면 "soe" 선수가 추월한 것을 의미하여 순위는 "soe", "mumu", "poe"라고 할 수 있습니다.

매개변수는

1. 현재 등수 순서대로 담긴 문자열 배열 players

2. 해설진이 부른 이름을 담은 문자열 배열 callings

 

answer 배열에 경주가 끝났을 때 선수들의 이름을 순서대로 담에 return 해줍니다.

 

 

입출력 예

players = ["mumu", "soe", "poe", "kai", "mine"]

callings = ["kai", "kai", "mine", "mine"]

result = ["mumu","kai", "soe", "mine", "poe"]

 

접근 방법 ( 알고리즘 )

- 첫번째 ( 오답 )

answer을 players와 복사하여 동일한 배열을 생성해줍니다. 

추월한 선수의 배열(callings)을 하나하나 읽을 때마다 answer의 값을 바꿔줍니다.

추월한 선수의 index값과 추월 선수 이름, 추월당한 선수의 인덱스는 추월한 선수의 index-1값과 선수 이름을 저장할 변수 생성합니다.

그리고 answer에 추월한 선수와 추월당한 선수의 이름을 다시 저장합니다.

import java.util.Arrays;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        answer = players.clone(); // 순위 복사하여 답 배열 생성
        
        for (int i = 0; i<callings.length; i++){
            String faster = callings[i]; //추월한 사람의 이름
            int fasterRank = Arrays.asList(answer).indexOf(callings[i]); // 추월한 사람의 원래 랭킹
                        
            int loserRank = fasterRank-1; // 추월당한 사람의 랭킹
            String loser = answer[loserRank]; // 추월당한 사람의 이름

            // 순위 바꿔주기
            answer[loserRank] = faster; 
            answer[fasterRank] = loser;
            
        } 

        return answer;
    }
    
}

여기에서 문제점!! 

만약에 많은 선수가 있고 추월한 선수의 값이 계속 바뀌고 연속적으로 많을 때는 어떻게 처리할 것인가요???

이런 테스트 케이스에서 시간 초과가 일어났습니다...

첫번째에 짰던 코드는 바보같이 무턱대고 때려박는 식이라서 overflow 오류가 생성됩니다.

이런 경우에는 새로운 알고리즘이 필요합니다.

 

 

-두번째

각 선수별로 index 값을 불러와 저장해둡니다.

callings의 배열에서 값이 몇번 불리는 지 체크합니다. 단 다음에 부르는 값이 동일하면 -1을 추가로 더해줍니다. 

아니라면 일반적인 -1을 해줍니다.

위의 경우에 따라서 추월당한 선수들의 index값은 +1을 해줍니다.

그리고 answer의 해당하는 index값에 선수들의 이름을 추가합니다.

그러면 되지 않을 까....?

하지만...!

이부분도 또한 위와 같이 오류가 날것 같다.

 

-세번째

다른 블로그의 도움으로 HashMap을 사용하기로 한다!

예전에 배웠던 HashMap을 다시 상기시키면서 차근차근 공부했다

key 값으로 value값을 가지고 올 수 있다는 장점을 가지고 있다

(HashMap의 개념을 다시 정리해서 올리겠습니당)

key값을 가지고 있으므로 value값도 쉽게 읽어올 수 있다

그리고 읽어온 그대로 넣으면 된다!

import java.util.Arrays;
import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = {};
        answer = players.clone(); // 동일한 배열의 조건으로 만들어야하기 때문에 players 배열 복사
        
        HashMap<String, Integer> playerName = new HashMap<>(); // key:선수이름, value:인덱스
        HashMap<Integer, String> playerRank = new HashMap<>(); // key:인덱스, value:선수이름
        
        for (int i=0; i<players.length; i++){
            playerName.put(players[i], i); // key 값에 플레이어 이름을 넣음
            playerRank.put(i, players[i]); // key 값에 플레이어 순위을 넣음
        }
        
        for (int i=0; i<callings.length; i++){
            // 추월한 유저 순위
            // 추월당한 유저 순위
            int fasterRank = playerName.get(callings[i]); // 추월한 선수의 Integer값
            String slower = playerRank.get(fasterRank-1); // 추월당한 선수의 이름
            
            // 바꾸기
            playerName.put(callings[i],fasterRank-1);
            playerName.put(slower, fasterRank);
            
            playerRank.put(fasterRank-1, callings[i]);
            playerRank.put(fasterRank, slower);          
        }
        
        for (Integer i:playerRank.keySet()){ // answer에 저장
            String name = playerRank.get(i);
            answer[i]=name;
        }
            
        return answer;
    }
    
}

이렇게 작성하였습니다!

 

너무 귀엽당..

 

참고

https://velog.io/@ljs0429777/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%AC%EB%A6%AC%EA%B8%B0-%EA%B2%BD%EC%A3%BC

프로그래머스 - 달리기 경주

https://kadosholy.tistory.com/120

[Java] 자바 - HashMap 사용방법 (개념, 특징, 메소드 및 예제)