[프로그래머스] 달리기 경주 - 시간 복잡도를 꼭 고려해야 하는 문제 (Java)

달리기 경주

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

프로그래머스

 

사실 로직은 쉽게 생각했는데.. 계속 효율성에서 컷당해서 오래 걸렸다 ㅜㅜ 사실 그 동안 시간 복잡도에 대해서 잘 모르고 직감으로 이 정도면 되겠지 하고 코드를 짰는데 시간 복잡도의 중요성을 아주 아주 잘 알게 해준 문제였다.

그리고 자료 구조에 대해서도 다시 정리해야겠다는 생각이 들었다. (면접에서 자료구조를 물어봤는데 잘 대답을 못했닿ㅎ)

 

첫 번째로 짰던 코드는 HashMap을 사용하였다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
        /*문제 이해
        계속 순서가 바껴야하므로 그냥 hashmap을 만들어서 [name, index] 를 담고,
        마지막에 sort하는 게 편할 것 같음
        */
        Map<String, Integer> map = new HashMap<>();
        for (int i=0; i<players.length; i++) {
            map.put(players[i], i);
        }
        
        for (int i=0; i<callings.length; i++) {
            map.put(getKey(map, map.get(callings[i])-1), map.get(callings[i]));
            map.put(callings[i], map.get(callings[i])-1);
        }
        
        for (int i=0; i<players.length; i++) {
            answer[i] = getKey(map, i);
        }

        
        return answer;
    }
    
    public static <K, V> K getKey(Map<K, V> map, V value){
        for (Map.Entry<K, V> entry: map.entrySet()){
            if (value.equals(entry.getValue())) {
                return entry.getKey();
            }
        }
        return null;
    }
}

-> getKey 메서드가 맵을 순회하는 선형탐색이기 때문에 시간 복잡도가 O(N^2)이다.

 

두 번째로 짰던 코드는 list를 만들어서 풀었다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {

        List<String> list = new ArrayList<>();
        for (int i=0; i<players.length; i++) {list.add(players[i]);}
        
        for (int i=0; i<callings.length; i++) {
            int now = list.indexOf(callings[i]);
            Collections.swap(list, now-1, now);
        }
        return list.toArray(new String[players.length]);
    }
}

이 코드는 .indexOf 메서드의 시간 복잡도는 O(N)인데, callings 배열의 길이만큼 반복하므로 callings 배열의 길이를 M이라고 하면 O(M*N)이 된다. 이전 코드보다 효율성은 늘었으나, M의 길이가 길어진다면 효율성이 떨어져서 탈락한 것 같다.

 

세번째로 짰던 코드는 LinkedList로 해보았다. (자료구조를 잘못 사용했나 싶어서 다 했던 것 같다 ..)

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        LinkedList<String> list = new LinkedList<>(Arrays.asList(players));

        for (String calling : callings) {
            int now = list.indexOf(calling);
            list.remove(now);
            list.add(now - 1, calling);
        }
        return list.toArray(new String[players.length]);
    }
}

근데 이 코드도 indexOf 메서드를 쓰게 되어서 여전히 같았다.

네 번째 코드도 마찬가지였다.

class Solution {
    public String[] solution(String[] players, String[] callings) {
        List<String> list = new ArrayList<>(Arrays.asList(players));
        int size = list.size();

        for (String calling : callings) {
            int index = list.indexOf(calling);
            if (index > 0) {
                String temp = list.get(index);
                list.set(index, list.get(index - 1));
                list.set(index - 1, temp);
            }
        }

        return list.toArray(new String[size]);
    }
}

 

단순히 list로 하면 코드가 훨씬 짧아져서 이게 맞을 줄 알고 list로 계속 시도했지만, 효율성 테스트를 통과할 수가 없었다. 

뒤늦게 찾아보니까 List는 요소의 추가 및 제거에는 효율적인 자료구조지만, indexOf처럼 특정 요소를 탐색하는 데에는 선형 탐색을 해야해서 성능이 저하될 수 있다. 그렇기 때문에 다시 map으로 돌아가서 코드를 짜보기로 했다.

 

그래서 다섯번째로 코드를 짤 때는 첫 번째로 짠 코드와 같으나, getKey 메서드를 쓰지 않는 방법을 모색했다.

import java.util.*;

class Solution {
    public String[] solution(String[] players, String[] callings) {
        String[] answer = new String[players.length];
 
        Map<String, Integer> map = new HashMap<>();
        for (int i=0; i<players.length; i++) {map.put(players[i], i);}
        
        Map<Integer, String> reversedMap = new HashMap<>();
        for (int i=0; i<players.length; i++) {reversedMap.put(i, players[i]);}
     
        for (int i=0; i<callings.length; i++) {
            int currentIndex = map.get(callings[i]); //그 학생의 순위-1
            map.put(reversedMap.get(currentIndex-1), currentIndex); //이전 학생의 순위 +1
            reversedMap.put(currentIndex, reversedMap.get(currentIndex-1));
            map.put(callings[i], currentIndex-1); //현재 학생의 순위 -1
            reversedMap.put(currentIndex-1, callings[i]);
        }
        
        for (int i=0; i<players.length; i++) {answer[i] = reversedMap.get(i);}

        return answer;
    }
}

위에서도 말했듯이, getKey 메서드는 맵을 순회하며 값에 해당하는 키를 찾는다. 이는 선형 탐색으로 O(N)의 시간 복잡도를 가진다. 그래서 최종적으로 O(N^2)의 시간 복잡도를 가지게 되어서 효율성 테스트에서 탈락하였다.

그래서 getKey 메서드를 쓰지 않는 대신에, value값을 가져오는 것은 빠르다는 것을 사용해보았다. (key로 value값을 가져오는 것은 빠르게 가능하다. (시간 복잡도 O(1)) HashMap은  key와 value의 매핑관계를 유지하고 있기 때문이다.)

이전 map의 key value값을 뒤집은 reversedMap 만들어서 시간 복잡도를 O(N+M) (N은 players 배열의 크기, M은 callings 배열의 크기)로 줄여서 겨우 통과할 수 있었다.