[프로그래머스 Lv1] 완주하지 못한 선수 | 자바

문제

완주하지 못한 선수

풀이 1

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        ArrayList<String> compList = new ArrayList<>(Arrays.asList(completion));

        for(String part : participant) {
            int idx = compList.indexOf(part);

            if(idx != -1) {
                compList.remove(idx);
            } else {
                return part;
            }
        }

        return "";
    }
}

• 처음 풀이입니다.
• 정확성 테스트 케이스는 통과했지만, 효율성 테스트에서 시간 초과가 나와 오답 처리 되었습니다.
• 그 이유는 indexOf와 remove가 O(N)의 시간 복잡도를 갖고, for문 안에 중첩해서 사용했기 때문의 최악의 경우 O(N^2)이 나올 수 있기 때문입니다.

풀이 2

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);

        for(int i = 0; i < completion.length; i++) {
            if(!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }

        return participant[participant.length - 1];
    }
}

• 배열을 이용해서 풀 수 있습니다.

풀이 3

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();

        for(String part : participant) {
            map.put(part, map.getOrDefault(part, 0) + 1);
        }

        for(String comp : completion) {
            map.put(comp, map.get(comp) - 1);
        }

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

        return "";
    }
}

• 문제 주제가 해시였기 때문에, 해시로도 풀이 했습니다.