[Programmers] 완주하지 못한 선수

문제 파악

participant에는 있지만 completion에는 없는 사람을 찾기

접근 방법

1. 정렬이용

1. 정렬을 하여 두 배열을 탐색할 수 있도록 설정
2. 완전 탐색을 통해 같은지 판단. 다른 순간이 나오는 경우 완주 하지 못 한 사람이 있음

1. HashMap이용

1. HashMap으로 이용하여 completion의 이름과 동명이인의 명 수를 저장
2. participant을 탐색하며 HashMap에 있는지 지금까지 몇 명을 찾았는 지를 파악 3-1) HashMap의 value가 0인 경우 동명이인이 들어왔고 본인은 못 들어왔음으로 완주하지 못함. 3-2) HashMap에 없을경우 완주 하지 못 한 사람

코드 구현

/**
     * 정렬을 활용
     * 정렬 시 문자열 자체도 비교해야하는 시간이 소모되므로 상대적으로 오래 걸린다.
     * */
    class Solution {
        public String solution(String[] participant, String[] completion) {
            String answer = "";
            Arrays.sort(participant);
            Arrays.sort(completion);
            for(int i=0; i<completion.length; i++){
                if(!completion[i].equals(participant[i])){
                    return participant[i];
                }
            }
            return participant[participant.length-1];
        }
    }
/**
 * HashMap 이용
 * */
class Solution2 {
    public String solution(String[] participant, String[] completion) {
        HashMap<String,Integer> counter = new HashMap<>();
        for(String c: completion){
            counter.put(c, counter.getOrDefault(c, 0) + 1);
        }
        for(String s: participant){
            if(!counter.containsKey(s) || counter.get(s)==0){
                return s;
            }
            counter.compute(s, (k, v) -> v - 1); //람다 표현식 (key,value), compute()를 통해 키 s의 값을 재계산하여 맵에 저장
        }
        return participant[participant.length-1];
    }
}

 

배우게 된 점

• 완전 탐색 시 HashMap 탐색시간을 줄일 수 있다.