[프로그래머스/42576] 완주하지 못한 선수

18 Jan 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이
  • 두 번째 풀이

☑️ 문제

프로그래머스 42576

☑️ 풀이

• HashSet 카테고리에 있는 문제라, HashSet을 사용해서 풀려고 했다.

• 처음에는 completion의 모든 선수를 HashSet에 넣은 뒤, participant의 모든 선수를 HashSet에 넣어 마지막에 남은 한 명을 출력하려고 했다. 하지만 계속 통과하지 못해 문제를 다시 읽어보니 아래와 같이 동명이인인 선수들도 있을 수 있다는 걸 확인했다.

    participant = {mislav, mislav, stanko, stanko, ana}
    completion = {mislav, mislav, stanko, ana}
  

첫 번째 풀이

//시간: 1.29ms
//메모리: 84.4MB

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {

        String answer = "";
        Set<String> set = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();

        int cnt = 0;
        for (int i = 0; i < completion.length; i++) {
            set.add(completion[i]);
            cnt++;
            if (set.size() == cnt) {
                map.put(completion[i], 1);
            } else {
                map.put(completion[i], map.get(completion[i]) + 1);
                cnt--;
            }
        }

        int size = set.size();
        for (int i = 0; i < participant.length; i++) {
            set.add(participant[i]);

            if (set.size() == size) {
                if (map.get(participant[i]) != 1) {
                    map.put(participant[i], map.get(participant[i]) - 1);
                } else {
                    set.remove(participant[i]);
                    size--;
                }
            } else {
                size++;
            }
        }

        Iterator iter = set.iterator();
        while (iter.hasNext()) {
            answer = iter.next().toString();
        }

        return answer;
    }
}

• Map을 이용해서 completion에 있던 선수들의 수를 모두 체크했다.
• participant의 모든 선수를 HashSet에 넣을 때 Map의 value값과 비교한다.
  • value가 1이 아닌 경우, 동명이인이기 때문에 value의 값만 1 감소시킨다.
  • value가 1인 경우, 동명이인이 아니기 때문에 Set에서 삭제한다.

• 이 과정을 거쳐 반복문을 끝까지 돌면 HashSet에는 완주하지 못한 선수만 남게 된다.

  

두 번째 풀이

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // HashMap에 완주자 저장 (key - 이름, value - 개수)        
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < completion.length; i++) {
            map.put(completion[i], map.getOrDefault(completion[i], 0) + 1);
        }
        
        String answer = "";
        // HashMap에 참가자 이름이 없거나, value가 0인 경우 -> 리턴
        for (int i = 0; i < participant.length; i++) {
            if (!map.containsKey(participant[i]) || map.get(participant[i]) == 0) {
                answer = participant[i];
                break;
            } else {
                map.put(participant[i], map.get(participant[i]) - 1);
            }
        }
        
        return answer;
    }
}

• HashMap만 사용해서 풀었다.
• 먼저 HashMap에 완주자를 먼저 저장했다.
  • Key는 완주자 이름, Value은 이름 수(동명이인 체크용)
• 그리고 참가자 배열을 돌면서 아래 두 가지 경우에 해당하는 지를 먼저 체크했다.
  1. HashMap의 Key에 참가자 이름이 없는지
  2. 참가자 이름이 있다면, HashMap의 Value 값이 0이 아닌지
     • 이 두 가지 중 하나라도 해당된다면 완주하지 못한 선수이기 때문에 이름을 리턴한다.
     • 해당되지 않는다면 HashMap의 Value 값을 하나 줄인다.
• 시간 복잡도
  • HashMap에 완주자 추가 → O(N-1)
  • HashMap에서 참가자 제외 → O(N)
  • 최종 시간 복잡도 → O(2N -1) → O(N)