문제

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

---

풀이

해결 방법: 해시맵 활용

해시맵의 구조

• 키(key): 참가자의 이름
• 값(value): 이름이 같은 참가자의 수
  • 이를 통해 동명이인 문제도 해결 가능

해결 과정

1. 참가자 목록 처리
   • 참가자 배열을 순회하며 각 참가자의 이름을 해시맵에 추가한다.
   • 이름이 이미 해시 맵에 있다면, 그 값(참가자 수)을 1 증가시킨다.
2. 완주자 목록 처리
   • 완주자 배열을 순회하면서 각 완주자의 이름을 해시 맵에서 찾아 값을 1 감소시킨다.
   • 완주하지 못한 참가자의 이름에 해당하는 값은 0이 아닌 수가 된다.
3. 완주하지 못한 참가자 찾기
   • 해시 맵을 순회하면서 값이 0이 아닌 첫번째 key(참가자 이름)을 찾는다.

Q. 🧐 해시맵에서 값으로 조회하는 것은 비효율적이지 않을까?
A. 마지막 4번에서 완주하지 못한 참가자를 찾는데 최악의 경우 O(N)이 걸리게 된다. 완주하지 못한 참가자는 단 한명이므로, 해시 맵을 순회하며 0이 아닌 첫 번째 값을 찾으면 즉시 순회를 중단할 수 있어 실행시간은 빠른 편이다. (특히 내가 먼저 구현했던 ArrayList를 이용한 것에 비하면...)

💻 결과코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
    	HashMap<String, Integer> participants = new HashMap<String, Integer>();
        
    	// 참가자 명단을 해시맵에 추가
        for (String player : participant) {
        	participants.put(player, participants.getOrDefault(player, 0) + 1);
        }
        
        // 완주자 명단을 통해 참가자 명단에서 제거
        for (String player : completion) {
        	participants.put(player, participants.get(player) - 1);
        }
        
        // 해시맵에서 값이 0이 아닌 참가자를 찾음
        for (String player : participants.keySet()) {
        	if (participants.get(player) == 1) {
        		return player;
        	}
        }
        
        // 이론상 도달하지 않음
        return null;
    }
}

• 해시맵의 주요 연산인 삽입(put), 조회(get), 값 갱신은 평균적으로 O(1)의 시간 복잡도를 가진다. 해시 충돌이 발생하지 않는 이상, 이러한 연산은 매우 빠르다.
  • 참가자 배열을 순회하며 해시맵에 추가(put)하는 작업: 각 참가자마다 평균 O(1)
  • 완주자 베열을 순회하며 해시맵에서 감소(put to update)하는 작업: 각 완주자마다 평균 O(1)
  • 최종적으로 해시맵을 순회하며 완주하지 못한 참가자를 찾는 작업: 각 요소를 처리하는 시간은 평균 O(1)
• 전체 시간 복잡도: O(N)

오답코드

내가 처음 아무 생각없이 ArrayList를 사용해서 작성한 코드다. 시간소요에서 문제를 통과하지 못했다.

• ArrayList에서 특정 요소를 찾는 작업(contains)과 요소를 제거하는 작업(remove)은 리스트의 크기에 비례하는 시간이 걸린다.
• 즉, 리스트에 N개의 요소가 있다면, 이 작업들의 시간 복잡도는 O(N)이다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        List<String> strList = new ArrayList<>(Arrays.asList(participant));
        
        for (String str : completion) {
            if(strList.contains(str)) {
                strList.remove(str);
            }
        }
        
        return strList.get(0);
    }
}

• contains(str)
  • 완주한 선수의 이름을 찾기 위해, 리스트의 처음부터 끝까지 순회해야 한다.
  • 최악의 경우 모든 요소를 확인해야 하므로, 이 작업의 시간 복잡도는 O(N)이다.
• remove(str)
  • 요소를 제거하는 경우에도 해당 요소의 위치를 찾아야 하며, 이후 리스트의 나머지 부분을 조정해야 한다.
  • 이 작업 역시 O(N)의 시간 복잡도를 가진다.
• 결과적으로 코드의 전체 시간 복잡도는 O(N^2)이 된다.
  • 완주자 배열을 순회하며 contains와 remove를 호출할 때마다 O(N)의 시간이 소요되기 때문

📗 Hash

[자료구조] 해시(Hash) 알아보기