[프로그래머스, Java] 완주하지 못한 선수 (자료구조의 중요성)

1. 문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

* 제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

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];
    }
}

문제는 문제없이 통과되었으나, 시간복잡도 측면에서 오래걸리는 문제가 있어 다른 방법으로 풀 수 있는 방법에 대해 찾아보다, HashMap을 사용하면 시간복잡도를 줄일 수 있다는 것을 알게 되었다.

🔅 HashMap을 사용한 풀이

import java.util.*;

class Solution {
	public String solution(String[] participant, String[] completion) {
		HashMap<String, Integer> map = new HashMap<>();
		
		for (String str : participant) {
			map.put(str, map.getOrDefault(str, 0) + 1);
		}
		
		for (String str : completion) {
			map.put(str, map.get(str) - 1);
		}
		
		for (String key : map.keySet()) {
			if (map.get(key) > 0) {
				return key;
			}
		}
		return "";
	}
}

✅ 접근법

1. 참가자 전원을 Map에 저장
   map.getOrDefault(key, default) : map에 값을 넣을 때, 값이 없으면 0을 넣음
2. 완주자들을 map에서 찾아 값을 줄임
   map.get(key) : key값의 value를 가져옴
3. 최종 Map에서 값이 1인 Key값을 return!
   map.keySet() : map의 모든 Key 집합을 가져옴

스스로 푼 방식의 시간복잡도
: 정렬 + 선형 탐색 = O(nlogn) + O(n) = O(nlogn)

• 정렬에는 비교 연산이 존재

HashMap으로 푼 방식의 시간복잡도
: 해시 탐색 = O(n)
HashMap의 put / get 연산 : 평균 O(1)

• HashMap에서 값을 찾을 때엔 비교 연산 없이 해시값 계산 후 바로 접근

HashMap은 key를 바로 저장하지 않고, key → 해시값 → 배열 인덱스로 변환
➡️ 값을 찾기 위해 처음부터 끝까지 탐색하지 않고, 계산 한 번으로 들어갈 자리를 앎
따라서, 시간복잡도는 평균 O(1), 최악 O(n)이 됨

3. 깨달은 점

문제에 대해 접근할 때, 데이터를 어떻게 저장하고 접근할지에 대해 먼저 고민을 하자.
각 자료구조의 특징을 잘 파악해도 시간 복잡도 측면에서 큰 이득을 얻을 수 있다!