[프로그래머스] 완주하지 못한 선수 - 42576(Java)

문제 URL

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

문제 설명

이 문제는 마라톤에 참가한 선수와 완주한 선수의 명단이 주어졌을 때, 완주하지 못한 선수를 찾아내는 것입니다.

• participant 배열은 참가자 명단을,
• completion 배열은 완주자 명단을 제공합니다.

모든 참가자는 단 한 번씩만 완주하거나 실패하며, 한 명의 선수가 중복으로 참가할 수 있습니다.

---

나의 풀이

기본 풀이

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> hashmap = new HashMap<>();
        
        // 참가자 배열을 순회하며 이름과 빈도를 저장
        for(String str : participant){
            hashmap.put(str, hashmap.getOrDefault(str, 0) + 1);
        }

        // 완주자 배열을 순회하며 값을 감소
        for(String str : completion){
            hashmap.put(str, hashmap.get(str) - 1);
        }

        // HashMap에서 값이 0보다 큰 이름 반환
        for(String key: hashmap.keySet()){
            if(hashmap.get(key) > 0){
                return key;
            }
        }

        return ""; // 모든 선수가 완주한 경우 (문제에서는 발생하지 않음)
    }
}

풀이 설명

1. 참가자 배열 순회: 각 참가자의 이름을 HashMap에 추가하며 등장 빈도를 기록합니다.
2. 완주자 배열 순회: 각 완주자의 이름을 HashMap에서 찾아 값을 감소시킵니다.
3. 완주하지 못한 선수 찾기: HashMap을 순회하며 값이 0보다 큰 이름을 반환합니다.

---

개선 풀이

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> hashmap = new HashMap<>();
        
        // 완주자 배열을 먼저 HashMap에 추가
        for (String str : completion) {
            hashmap.put(str, hashmap.getOrDefault(str, 0) + 1);
        }

        // 참가자 배열을 순회하며 값을 감소
        for (String str : participant) {
            if (hashmap.getOrDefault(str, 0) == 0) {
                return str; // 완주하지 못한 선수
            }            
            hashmap.put(str, hashmap.get(str) - 1);
        }

        return ""; // 모든 선수가 완주한 경우 (문제에서는 발생하지 않음)
    }
}

개선 포인트

• 완주자 배열을 먼저 HashMap에 저장한 후, 참가자 배열에서 값을 감소시키며 바로 결과를 반환합니다.
• 값이 0보다 작아지거나 HashMap에 없는 이름이 발견되면 즉시 반환하므로, HashMap 순회를 생략할 수 있습니다.

---

결론

두 풀이 모두 시간 복잡도는 O(n)이지만, 개선 풀이가 더 간결하고 효율적입니다.