[Algorithm] 달리기 경주

프로그래머스

첨에는 그냥 간단하게 풀 수 있을 줄 알았는데,

public String[] solution(String[] players, String[] callings) {
    for(int i = 0; i < callings.length; i++){
        String calling = callings[i];
        for(int j = 1; j < players.length; j++){
            if(players[j].contentEquals(calling)){
                String temp = players[j-1];
                players[j-1] = players[j];
                players[j] = temp;
            }
        }
    }
    return players;
}

테스트 9부터 시간초과 발생??

 

 

이중 반복문으로는 해결할 수 없을 것 같아 HashMap을 이용해 풀어 보았다.

public String[] solution(String[] players, String[] callings) {
    HashMap<String, Integer> rankingMap = new HashMap<>();
    for(int i = 0; i < players.length; i++){
        String player = players[i];
        rankingMap.put(player, i);
    }
    for(String calling : callings){
        int rank = rankingMap.get(calling);
        int upRank = rank -1;
        rankingMap.put(calling, upRank);
        int downRank = rankingMap.get(players[upRank]) + 1 ;
        String downPlayer = players[upRank];
        rankingMap.put(downPlayer, downRank);
        players[upRank] = calling;
        players[downRank] = downPlayer;
    }
    return players;
}

1. HashMap에 플레이어들의 이름과 순위를 각 각 key와 value로 넣어 준다.

 

2. 이름이 불릴 때마다 HashMap에서 불린 선수와 그 앞의 선수의 순위를 바꿔준다.

 

3. 순위에 맞게 배열에 적용한다.