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

 

 

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

입출력 예

 

 

풀이1. 정렬과 zip을 활용한 미완주자 찾기

def solution(participant, completion):
    
    participant.sort()
    completion.sort()
    
    z = list(zip(participant, completion))
    for a,b in z:
        if a != b:
            return a
    return participant[-1]

 

 

정렬을 이용한 이 방법의 시간 복잡도는 다음과 같은 단계로 분석할 수 있다.

1. 정렬: participant와 completion 배열을 각각 정렬하는 데 걸리는 시간 복잡도는 일반적으로 O(Nlog⁡N)이다. 여기서 N은 participant 배열의 길이이며, completion 배열의 길이는 N−1이다.
   • 두 배열을 정렬하는 데 각각 O(Nlog⁡N)과 O((N−1)log⁡(N−1))의 시간이 걸리지만, 근사적으로 O(Nlog⁡N)으로 표기할 수 있다. 이는 가장 큰 시간 복잡도 항을 기준으로 표기하는 것이기 때문이다.
2. 비교: 정렬된 두 배열을 처음부터 끝까지 순회하면서 서로 비교하는 과정은 O(N) 시간 복잡도를 가진다. 정렬된 배열을 차례로 비교하기 때문에, 요소 하나마다 상수 시간 O(1)에 비교할 수 있다. 두 배열을 끝까지 순회하면서 비교하는 데 걸리는 시간은 O(N)이다.
3. 최종 시간 복잡도: 위의 과정을 합산하면 전체 시간 복잡도는 다음과 같다.

• O(Nlog⁡N)+O(N) =O(NlogN)
• 따라서, 이 방법의 시간 복잡도는 O(Nlog N)이다.

 

 

풀이2. Counter를 활용한 미완주자 찾기

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

 

1. Counter 생성: collections.Counter(participant)와 collections.Counter(completion)을 생성하는 과정의 시간 복잡도는 각각 O(N)과 O(N−1)이다.

• Counter는 내부적으로 배열의 모든 요소를 순회하며 각 요소의 개수를 해시 테이블로 저장한다.
• 따라서 participant와 completion 배열의 길이에 비례한 시간이 걸리며, 근사적으로 O(N)로 표현할 수 있다.

2. Counter 간 차감 연산: Counter(participant) - Counter(completion) 연산은 두 Counter 객체의 키를 비교하고 값을 차감하는 과정이다.

• 이 과정은 participant의 요소를 기준으로 실행되며, 시간 복잡도는 O(N)이다.
• 각 키에 대해 상수 시간 O(1)에 차감 연산이 이루어지기 때문에 전체 차감 연산의 시간은 O(N)이다.

3. 결과 반환: list(answer.keys())[0]을 실행하는 과정은 O(1)이다.

• 차감 결과에서 하나의 키를 가져오는 작업은 상수 시간에 수행된다.

4. 최종 시간 복잡도: 위의 과정을 합산하면 전체 시간 복잡도는 다음과 같다.

• O(N)+O(N)+O(1)=O(N)
• 따라서, 이 방법의 시간 복잡도는 O(N)이다.