프로그래머스: 완주하지 못한 선수 찾기

문제 해결

참가자 목록과 완주자 목록을 HashMap을 활용하여 비교하는 방식입니다. 구체적으로, 참가자 목록에 등장하는 각 선수의 이름과 등장 횟수를 카운팅하고, 완주자 목록을 이용해 그 수를 하나씩 차감해 나가는 방식입니다. 결국, 남은 수가 1인 선수는 완주하지 못한 선수입니다.

1. HashMap 초기화
   먼저, 참가자 목록에 등장하는 각 선수의 이름과 등장 횟수를 카운팅합니다. HashMap을 사용하여 선수의 이름을 키로, 등장 횟수를 값으로 저장합니다.
2. 완주자 목록 처리
   완주자 목록을 하나씩 순회하면서, 완주한 선수의 이름을 HashMap에서 찾아 그 값(등장 횟수)을 하나씩 감소시킵니다.
3. 결과 추출
   HashMap에서 값이 1인 선수는 완주하지 못한 선수이므로, 해당 선수를 결과로 반환합니다.

코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String result = "";

        // HashMap을 사용하여 참가자 목록의 각 선수 이름과 등장 횟수를 카운팅
        Map<String, Integer> map = new HashMap<>();
        for (String s : participant) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

        // 완주자 목록에서 등장하는 선수의 등장 횟수를 차감
        for (String s : completion) {
            map.put(s, map.get(s) - 1);
        }

        // 값이 1인 선수 찾기
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 0) result = entry.getKey();  // 남은 값이 1인 선수
        }

        return result;
    }
}

 

 

1. map.put(s, map.getOrDefault(s, 0) + 1)
   이 코드는 participant 배열의 각 선수 이름을 HashMap에 추가하는 부분입니다. getOrDefault(s, 0)는 해당 선수가 이미 등장했는지 확인하고, 등장하지 않았다면 0을 반환하여 선수의 등장 횟수를 1씩 증가시킵니다.
2. map.put(s, map.get(s) - 1)
   완주자 목록에서 각 선수의 이름을 찾아 HashMap에 저장된 등장 횟수를 1 감소시킵니다. 이 작업을 통해 완주한 선수의 이름은 등장 횟수가 0이 됩니다.
3. for (Map.Entry<String, Integer> entry : map.entrySet())
   최종적으로 map을 순회하면서 값이 1인 선수를 찾습니다. 값이 1인 선수는 완주하지 못한 선수입니다.

 

시간 복잡도

• 참가자 목록과 완주자 목록을 순회하면서 HashMap에 값을 추가하고 조회하는 작업은 각각 O(n)과 O(m) 시간이 걸립니다. 여기서 n은 참가자 수, m은 완주자 수입니다.
• 최종적으로 map.entrySet()을 순회하는 작업은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n)입니다.