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

• 첫번째 풀이

import java.util.Hashtable;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Hashtable<Integer, String> ht = new Hashtable<>();
        for(int i=0; i<completion.length; i++){
            ht.put(i, completion[i]);
        }

        for(int i=0; i<participant.length; i++){
            if(!ht.containsValue(participant[i])){
                answer = participant[i];
                break;
            }
            if(ht.containsValue(participant[i])){
                for(int j=0; j<completion.length; j++){
                    if(ht.containsKey(j) && ht.get(j).equals(participant[i])){
                        ht.remove(j);
                        break;
                    }
                }
            }
        }

        return answer;
    }
}

효율성 측면에서 실패한 풀이. time complexity가 n^2이다.

그래서 다음과 같이 개선하였다.

• 알고리즘
  (1) part와 com를 각각 hashtable에 넣는다
  (2) key값이 name이고 value가 중복 수
  (3) 두 Hashtable을 비교할 때 part에 있는게 com에 없거나 value가 다르면 해당 key return

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        Arrays.sort(completion);
        Hashtable<String, Integer> part = new Hashtable<>();
        Hashtable<String, Integer> comp = new Hashtable<>();

        part.put(participant[0], 1);
        for(int i=1; i<participant.length; i++){
            if(participant[i-1].equals(participant[i])){
                part.replace(participant[i], part.get(participant[i])+1);
            } else {
                part.put(participant[i], 1);
            }
        }

        comp.put(completion[0], 1);
        for(int i=1; i<completion.length; i++){
            if(completion[i-1].equals(completion[i])){
                comp.replace(completion[i], comp.get(completion[i])+1);
            } else {
                comp.put(completion[i], 1);
            }
        }

        for(String k : part.keySet()){
            if(!comp.containsKey(k) || !part.get(k).equals(comp.get(k))){
                return k;
            }
        }

        return answer;
    }
}

contains와 containsKey의 차이? -> contains는 string method인데 containsKey인줄 알고 사용해서 논리 오류가 발생했었다.

→ 위 알고리즘에서 getOrDefault함수를 이용하면 하나의 hash로 해결 가능