[프로그래머스] Lv.1 : 완주하지 못한 선수 - 자바[Java]

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

프로그래머스

 

풀이

ArrayList를 사용한 풀이 - 효율성 문제

completion 배열의 요소를 ArrayList에 담은 후, for문을 사용해 participant의 각 요소에 대하여 list에 있는지 확인한다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        ArrayList<String> winners = new ArrayList<>();
        String answer = "";
        
        for (String name: completion) {
            winners.add(name);
        }
        
        for (String name: participant) {
            if (!winners.contains(name)) {
                answer = name;
                break;
            }
            winners.remove(name);
        }
        return answer;
    }
}

하지만 효율성 테스트에서 시간 초과가 떠서 실패했다.

시간 초과가 뜬 이유: 시간복잡도
list의 cotains()의 시간복잡도: O(n)
위 풀이는 각 참가자에 대해 contains()를 호출하므로 최대 n * n 번의 연산이 일어나고, n은 최대 10만이기 때문에, 10만 * 10만번의 연산이 일어나므로 시간 초과가 뜰 수 밖에 없다.

 

HashMap을 사용한 풀이 - 통과

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        String answer = "";
        
        for (String name: completion) {
            map.put(name, map.getOrDefault(name, 0) + 1);
        }
        
        for (String name: participant) {
            if (!map.containsKey(name)) {
                answer = name;
                break;
            }
            int num = map.get(name);
            map.put(name, --num);
            if (num < 0) {
                answer = name;
                break;
            }
        }
        return answer;
    }
}

 

Reference

JAVA Collection 시간 복잡도/특징 정리