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

https://school.programmers.co.kr/learn/courses/30/lessons/프로그래머스 : 달리기 경주

프로그래머스

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

        for(int i = 0; i < players.length; i++){
            answer[i] = players[i];
            System.out.println(answer[i]);
        }
        
        return answer;
    }
}

 

오늘은 알고리즘 문제를 풀어봤다. 너무 쉬운 문제다.

 

 

라고 생각했던 적이 있었다. 시간복잡도 문제가 발생했다. 좋은 해결책이 뭘까 생각했다.

곰곰이 생각해 보니, 시간복잡도가 최악일 경우, 한번 순서를 뒤집는 데에 10만 번 정도의 동작이 요구됐다.

여기서 내 기준으로는 두가지의 선택지가 있었다.

버블정렬을 시간복잡도가 낮은 다른 정렬로 바꾸거나, 자료구조를 활용하는 것이었다.

우선 두가지 방법 중, 간단한 해결책인 자료구조(Map)를 활용해봤다.

 

 

하지만 어떻게 구현해야 할지 막막했다.

처음에는 이름을 key값으로 구현하고, 이름이 불리면 등수를 조절하는 게 순탄치 않았다.

다음번엔 등수를 key값으로 하면 초반에 정의 시 입력되는 순서대로 등수를 부여하고,

이름 언급 시 앞의 플레이어와 현재 플레이어의 이름만 바꿔주면 될 것 같아 등수를 key값으로 설정하고 구현했다.

그렇게 여차저차하다 보니 두 개의 Map을 쓰게 됐다.  

 

import java.util.*;
class Solution {
    public String[] solution(String[] players, String[] callings) {
 		Map<Integer, String> rank = new HashMap<>();
        Map<String, Integer> player = new HashMap<>();

        for (int i = 0; i < players.length; i++) {
            rank.put(i + 1, players[i]);    
            player.put(players[i], i + 1);  
        }

        for (String calling : callings) {
            int backRank = player.get(calling);        
            int frontRank = backRank - 1;
            String frontPlayer = rank.get(frontRank);

            rank.put(frontRank, calling);
            rank.put(backRank, frontPlayer);
            player.put(frontPlayer, backRank);
            player.put(calling, frontRank);
        }

        String[] answer = new String[players.length];
        int cnt = 0;
        for(String value : rank.values()){
            answer[cnt++] = value;
        }
        return answer;
    }
}

List와 Set은 비교적 자주 사용하였으나 Map은 별로 사용하지 않아 구현할 때 어려움을 겪었다.

하지만 이 문제 덕에 Map에 대해 좀 더 자세히 알 수 있는 계기가 됐다.