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

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

프로그래머스

문제

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

풀이

달리기 결과를 return 하는 문제이다.

 

해결한 과정을 단계별로 나누면 다음과 같다.

1. callings에서 해설진이 부른 선수의 등수를 players 배열에서 찾는다.
2. 해당 선수와 바로 앞에 있는 선수의 등수를 바꾼다.
3. 1 ~ 2번을 callings의 원소 개수만큼 반복한다.

 

1번을 할 때, players 배열의 크기만큼 for문을 돌려서 찾았더니 시간초과가 발생했다.

그래서 HashMap에 players의 초기 정보를 저장하고 1 ~ 3단계를 진행하였더니 해결할 수 있었다.

 

---

🔔 틀린 코드(시간초과)

class Solution {
    public String[] solution(String[] players, String[] callings) {
        for(int i = 0; i < callings.length; i++) {
            for(int j = 0; j < players.length; j++) {
                if(players[j].equals(callings[i])) {
                    String tmp = players[j];
                    players[j] = players[j - 1];
                    players[j - 1] = tmp;
                    break;
                }
            }
        }
        
        return players;
    }
}

---

코드

import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
        HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
        for(int i = 0; i < players.length; i++) {
            hashmap.put(players[i], i);
        }
        
        for(int i = 0; i < callings.length; i++) {
            int callidx = hashmap.get(callings[i]);
            
            hashmap.put(callings[i], callidx - 1);
            hashmap.put(players[callidx - 1], callidx);
            
            players[callidx] = players[callidx - 1];
            players[callidx - 1] = callings[i];
        }
        
        return players;
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!