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

문제출처

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

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

 

먼저 효율성 검사에서 빵점을 맞은 코드

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        List<String> completion_list =  new ArrayList<String>(Arrays.<String>asList(completion));
        for(String p : participant){
            int idx = completion_list.indexOf(p);
            if(idx < 0){  
                answer += p;
                break; 
            }
            completion_list.remove(idx);
        }
        return answer;
    }
}

그래 명색이 대놓고 해시 문제인데 이건 아니겠지... 싶긴했다. (그래도 for문이 단 하나인데 설마 하는 기대를 쪼금 했다)

 

해시로 푼 코드 적기 전에 이것의 문제점을 적어놔야겠다 싶어서 블로그를 켰다.

우선 for문 안에서 사용되는 indexOf()함수의 시간 복잡도는 O(n)

list의 remove() 이것또한 시간복잡도가 O(n)이다. 그럼 여기서 또 list만큼 n번이 곱해지면 ....

그것도 for문은 participant 개수 만큼 돌기 때문에 이게 최대값인 10만이라면 정말 어마어마하게 오래걸릴것이다.

그렇다면 해시는?

 

 

해시를 사용해서 푼 코드

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> table = new HashMap<String, Integer>();
        for(String p : participant){
            if(table.containsKey(p)){
                table.put(p, table.get(p) + 1);
            }
            else{
                table.put(p, 1);
            }
        }
        for(String c : completion){
            table.put(c, table.get(c) - 1);
        }
        for(String key : table.keySet()){
            if(table.get(key) != 0){
                answer += key;
                break;
            }
        }
        return answer;
    }
}

해시의 경우에는 대부분 시간복잡도가 O(1)이다.

containsKey(), get() 등등...

따라서 시간이 굉장히 줄어드는걸 확인할 수 있다.

이는 해시에 대해서 다시 공부한 글을 첨부하겠다.