[프로그래머스] 완주하지 못한 선수 자바 해시 맵 활용

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

프로그래머스

문제

참가자명단 participant 와 완주자명단 completion이 있다.

completion에 없는 유일한 완주 실패자 이름을 찾아 반환하시오.

제한사항

동명이인이 존재할 수 있음.

접근

1. 완주자리스트를 리스트 compList로 변환한다.
2. 참가자명단을 순회하여 compList.contains로 이름을 찾는다.
3. 찾았으면, 해당 인덱스를 리스트에서 제거하고 못찾았으면 이름을 answer에 담아 반환한다.

public static String solution(String[] participant, String[] completion) {
        String answer = "";
        List<String> compList = new ArrayList<>(Arrays.asList(completion));
        for(String name : participant){
            boolean found = compList.contains(name);
            if(found){
                int idx = compList.indexOf(name);
                compList.remove(idx);
            } else {
                answer = name;
                break;
            }
        }

        return answer;
    }

발견된 문제

시간초과로 효율성 테스트에서 탈락.
추정 사유 :리스트의 contains()와 remove() 연산이 O(n) 시간 복잡도를 가져
전체 시간 복잡도가 O(n²)이 되어 시간 초과가 발생

 

수정

해시맵 방식으로 시간복잡도 효율화

public static String solution2(String[] participant, String[] completion) {
        Map<String, Integer> pMap = new HashMap<>();
        for(String name : participant){
            pMap.put(name, pMap.getOrDefault(name, 0) + 1);
        }

        for(String name : completion){
            int count = pMap.get(name);
            if(count == 1){
                //유일한 이름
                pMap.remove(name);
            } else {
                pMap.put(name, count -1);
            }
        }

        return pMap.keySet().iterator().next();
    }

알게된 점

1.해시맵의 조회 및 삽입은 평균 O(1) 시간 복잡도를 가져 리스트방식 O(n)보다 효율적이다.
2.맵에서 키 꺼내기 : map.keySet().iterator().next()