[프로그래머스/JAVA] 달리기 경주

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

풀이 방법

callings가 불릴 때마다, 해당 선수의 위치(n)와 그 앞자리(n-1)를 바꿔주기만 하면 끝나는 문제라고 생각했다.

제일 먼저 시도한 방법은 생각한 그대로를 표현한 2중 for문 구조이다.

 

내 코드(JAVA)

 

public String[] solution(String[] players, String[] callings) {
	// 해당 코드는 시간초과가 발생한다.
    for (String call : callings) {
        for (int i = 0; i < players.length; i++) {
            if (players[i].equals(call)) {
                String temp = players[i - 1];
                players[i - 1] = players[i];
                players[i] = temp;
                break;
            }
        }
    }

    return players;

}

 

해당 코드는 75점짜리 코드로, 대용량 데이터에서 시간초과가 발생한다.
데이터가 많아 배열이 길어질 만큼 탐색할 데이터도 당연히 길어지기 때문이다.

 인덱스를 통해 찾는 것이 아니라, 하나하나 다 방문 후 값을 꺼내 비교해야 하므로 느릴 수밖에 없다.

해결방법으로 Map을 사용하기로 했다.
Map을 사용하면 모든 값을 순차적으로 돌지 않아도 되고, Key에 이름을, Value에 인덱스를 보관하여 컨트롤하고자 했다. 

 

 

두 번째 코드(JAVA)

 

public static String[] solution(String[] players, String[] callings) {
    Map<String, Integer> map = new HashMap<>();

	// Map에 최초 상태를 저장(Key : 이름, Value : 순위(index))
    for (int i = 0; i < players.length; i++) {
        map.put(players[i], i);
    }

	// 1. 해설자가 부른 선수의 인덱스를 가져온다
    // 2. 해당 인덱스(n)를 활용하여, n-1 선수와 교환한다.
    // 3. 순위가 변경됐으니 map에도 해당 정보를 변경한다.
    for (String callName : callings) {
        int idx = map.get(callName);

        String temp = players[idx - 1];
        players[idx - 1] = callName;
        players[idx] = temp;

        map.put(callName, idx - 1);
        map.put(temp, idx);
    }

    return players;
}