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

접근 방식

마라톤 참가자 중 완주하지 못한 한 명을 찾는 문제를 해결해야 합니다.
일반적인 선형 탐색을 사용하면 최악의 경우 O(N²)의 시간이 걸릴 수 있으므로, 이를 최적화하기 위해 탐색에 O(1)이 걸리는 HashMap을 활용하는 방법을 선택했습니다.

 

어떻게, 카운팅을 해서 중복 참가자를 고려할 수 있을까요?

 

아래 예시를 통해 확인해 보겠습니다. (왼쪽 배열 : 참가자, 오른쪽 배열 : 우승자)

 

완주자를 기준으로 HashMap을 만들어 줍니다.

{ana=1, mislav=1, stanko=1}

 

참가자를 한명씩 확인하면서, 완주자를 확인합니다.

완주자 목록에 참가자가 존재하지 않는 경우 바로 정답으로 return해줍니다.

존재하는 경우엔 카운팅에 1을 빼줍니다.

 

잘 생각해보면, 동명이인이 완주를 하지 못한 경우엔 카운팅 갯수가 0인 상태를 조회하게 됩니다.

그와 달리 일반 완주자는 카운팅 갯수가 1인 상태를 조회하게 됩니다.

 

예시를 기준으로 흐름을 나타내면 다음과 같습니다.

{ana=1, mislav=1, stanko=1} --- 시작 전
{ana=1, mislav=0, stanko=1} --- 시작 mislav는 완주자 항목에 존재하므로 1을 빼줍니다.
{ana=1, mislav=0, stanko=1} --- stanko는 완주자 항목에 존재하므로 1을 빼줍니다.
{ana=1, mislav=0, stanko=0} --- 동명이인 mislav는 완주자 항목에 있긴 하지만, 카운팅 값이 0이됩니다.

 

풀이 코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> runner = new HashMap<>();
        
        for (String c : completion) {
            runner.put(c, runner.getOrDefault(c, 0) + 1);
        }

        for (String p : participant) {
            if (!runner.containsKey(p) || runner.get(p) == 0) {
                return p;
            }
            runner.put(p, runner.get(p) - 1);
        }
        
        return "";
    }
}

 

시간 복잡도

선형 탐색으로 인해서 O(N)이 걸립니다.

 

 

출력 결과