[Java] 프로그래머스_완주하지 못한 선수_해시

안녕하세요 루미너스입니다! 오늘은 프로그래머스 고득점 Kit 해시 문제를 풀어봤습니다.

 

문제

https://programmers.co.kr/learn/courses/30/lessons/42576#

코딩테스트 연습 - 완주하지 못한 선수

첫 번째 풀이 - List 이용, 시간초과

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // 참가자 명단을 ArrayList에 담습니다.
        List<String> list = new LinkedList<>();
        for (String participantName : participant)
            list.add(participantName);
        
        // 완주자 명단을 ArrayList에서 뺍니다.
        for (String completionName : completion)
            list.remove(completionName);
        
        // 첫 번째 요소를 반환합니다.
        return list.get(0);
    }
}

답은 맞았지만 시간초과가 나왔다.

왜 시간초과나 나왔을까? ArrayList의 add, remove 메소드의 시간복잡도를 찾아봤다.

찾아보니 ArrayList - add는 O(1)을 갖지만, remove의 경우 O(n)을 갖기 때문에 for문과 합쳐 O(n^2) 시간복잡도를 갖는다.

입력 데이터가 최대 100,000까지 올 수 있으니 100,000^2 = 100억이게 되고 1억 연산횟수일 때 1초이니 100초가 걸려 시간초과가 나게 된다.

 

LinkedList의 경우 add()는 O(1)이고 remove도 O(1)이다. 다만 remove()의경우 삭제할 노드의 참조를 알 경우 O(1)이다. 만약 순회하면서 삭제할 노드를 찾는다면 remove의 시간복잡도는 O(n)이 되어 마찬가지로 총 시간복잡도는 O(n^2)될 것이다.

 

두 번째 풀이 - HashMap , 성공

 

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 참가자 목록을 해시맵에 등록합니다. ket:이름 value:명
        for (String participantName : participant)
            map.put(participantName, map.getOrDefault(participantName,0) + 1);
        
        // 완주자 목록을 해시맵에서 뺍니다.
        for (String completionName : completion) {
            // 만약 value가 0이라면 엔트리를 삭제합니다.
            map.put(completionName, map.get(completionName) -1);
            if (map.get(completionName) == 0)
                map.remove(completionName);
        }
        
        Iterator it = map.keySet().iterator();
    
        return (String)it.next();
    }
}

다른 사람이 푼 코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

나는 값을 빼는 과정에서 0이되면 엔트리를 삭제하는 방식을 취했다. 반면 다른 풀이를 보면 더하는 과정과 빼는 과정을 끝낸 뒤에 key 집합을 가지고 value가 0이 아닌 key를 찾고 그 key를 반환하는 방식을 했다. 어떻게 보면 나는 2,3번째 과정이 엮여있었지만 다른 풀이를 보면 모두 역할에 따른 구현이 분리되어 가독성이 있어보인다. 좋은 알고리즘인거 같다.

 

느낀점

각 컬렉션 클래스들 메소드마다 시간복잡도가 어떻게 되는알 수 있었던 문제였다.

	add()	remove()	get()	contains()
ArrayList	O(1)	O(n)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(n)	O(n)

참고로 LinkedList의 삭제 연산 remove()는 삭제할 노드에 대한 참조를 가지고 있다는 가정하에 O(1)이다. 만약 순회하면서 지워야할 데이터를 찾아야된다면 remove의 시간복잡도는 O(n)이 된다.

참고

http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

Java Collections – Performance (Time Complexity)