[프로그래머스 lv1] 완주하지 못한 선수 (파이썬)

문제 설명

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

제한사항

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

입출력 예

입출력 예 설명

예제 #1
    "leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #2
    "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #3
    "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

---

첫 번째 시도

def solution(participant, completion):
    for item in completion:
        participant.remove(item)
    return participant[0]

첫 번째 채점 결과

가장 먼저 떠오른 completion 리스트의 아이템을 하나씩 participant 리스트에서 삭제하는 방법을 구현해보았다.

이렇게 쉽게 풀릴 거라 생각은 안했지만 역시 효율성 테스트에서 걸렸다.

 

두 번째 시도

def solution(participant, completion):
    answer = ''
    participant.sort() ; completion.sort()
    
    start, end = 0, len(completion) - 1 # 시작, 끝 인덱스 구하기
    mid = (end - start) // 2    # 중간 값 구하기
    
    while start <= mid and end >= mid:
        print('start :', start, 'mid :',mid, 'end :', end, 'mid값 :', participant[mid])
        if participant[mid] == completion[mid]: # 중간 값이 같은 경우
            start = mid + 1   
        else:   # 중간 값이 다른 경우
            end = mid - 1
        mid += (end - start) // 2 + 1
        
    if participant[mid] == completion[mid]:
        answer = participant[mid + 1]
    else:
        answer = participant[mid]
    
    return answer

두 번째 테스트 결과

두 번째 테스트에서는 이진 탐색을 생각해보았다.

두 리스트를 정렬해서 중간 값을 확인했을 때 두 값이 같다면 그 이전 인덱스의 값들은 모두 같은 것이라 생각하고 코드를 짰고, 코드 실행 결과 모두 부합했다.

두 번째 채점 결과

하지만 정확성 테스트에서도 모두 실패가 나왔고, 곰곰히 생각해보니 중간 값이 같을 때 그 이전 인덱스의 값들이 모두 같다는 가정이 틀렸다.

예를 들면 participant = [a, b, b, b] 이고, completion = [b, b, b] 일 때 participant[1] 과 completion[1] 이 모두 'b'로 같아서 그 이전 값들을 모두 일치한다고 판단하면 completion에 없는 'a' 참가자까지 모두 맞다고 판단하게 된다.

 

 

 

나의 풀이

def solution(part, comp):
    answer = ''
    part.sort(); comp.sort()
    
    # 중간 부분이 다른 경우
    for i in range(len(comp)):
        if part[i] != comp[i]:
            answer = part[i]
            break
    
    # 정렬 후 끝 부분이 다른 경우
    if answer == '':
        answer = part[len(comp)]
        
    return answer

그냥 첫 번째 시도에서 변형을 했다.

첫 번째 시도에서는 하나씩 제거했다면, 이 방법에서는 정렬 후 하나씩 비교했다.

파이썬의 정렬 알고리즘은 내부적으로 퀵 정렬을 사용하기 때문에 정렬 속도가 빠르다.

첫 번째 시도에서는 정렬되지 않은 리스트에서 아이템을 삭제하다 보니 리스트 전체를 탐색하면서 시간이 오래 걸렸다.

 

다만 마음에 걸리는 부분은 문제 유형을 해시로 했기 때문에 해시를 사용하지 않고 문제를 해결한 점이다.