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

🔗 문제 링크

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

📰 문제 요약

문제 설명, 입력, 출력, 조건 등 간략하게 정리

문제 설명

마라톤에서 단 한 명의 선수를 제외하고 모든 선수가 마라톤을 완주하였다

마라톤에 참여한 선수들이 담긴 배열과, 완주한 선수들의 이름이 담긴 배열이 주어질 때, 완주하지 못한 단 한 명의 함수를 반환

입력

마라톤에 참여한 선수들의 이름이 담긴 배열 participant

마라톤에 완주한 선수들의 이름이 담긴 배열 completion

• 1 ≤ 마라톤 경기에 참여한 선수의 수 ≤ 100,000
• completion의 길이 = participant의 길이 - 1
• 1≤ 참가자의 이름 ≤ 20 (알파벳 소문자)
• 참가자 중에 동명이인이 있을 수 있음

출력

완주하지 못한 선수의 이름

🔓 문제 접근 방식

기본 아이디어

• 전체 참가자 리스트와 완주한 사람의 리스트를 비교해서 만약 겹치는 사람이 있을 경우, 각 리스트에서 모두 삭제한다.
• 결국 마지막으로 남은 이름을 반환한다.

사용 알고리즘

• 해시

💻 구현 방법

1. completion 에 있는 사람이 participant에 있을 경우 각 리스트에서 전부 삭제
2. participant[0]의 값 반환

1차 시도

def solution(participant, completion):
    answer = ''
    for person in completion : # 완주한 사람
        if person in participant : # 참가자 명단에 있을 경우
            participant.remove(person) # 리스트에서 삭제
            completion.remove(person) # 리스트에서 삭제
        else : # 완주한 사람이 참가자 명단에 없을 경우,
            continue # 넘어감
    answer = participant[0] # 완주하지 못한 최종 1명 출력
    
    return answer

무엇이 문제인가 생각하다가, 주석을 달아보니 오류를 발견할 수 있었다.

참가자 리스트 > 완주자 리스트라서 for문에서 completion 에 접근하고, if문을 통해 participant 에 접근하는 방식으로 생각했는데, “완주한 사람이 참가자 명단에 없을 경우”가 아니라 “참가자 명단에 있는 사람이 완주자 명단에 없을 경우”를 생각해야 하므로, 뒤집혔다는 것을 알 수 있었다.

<aside> ❌

테스트 2

입력값 〉	["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]
기댓값 〉	"vinko"
실행 결과 〉	실행한 결괏값 "nikola"이 기댓값 "vinko"과 다릅니다.
</aside>

2차 시도

def solution(participant, completion):
    answer = ''
    for person in participant : # 완주한 사람
        if person in completion : # 참가자 명단에 있을 경우
            participant.remove(person) # 리스트에서 삭제
            completion.remove(person) # 리스트에서 삭제
        else : # 완주한 사람이 참가자 명단에 없을 경우,
            continue # 넘어감
    answer = participant[0] # 완주하지 못한 최종 1명 출력
    
    return answer

그래서 for문 과 if문 의 participant와 completion을 바꿔보았는데, 이번에는 테케 2개에서 오류가 발생하였다.

<aside> ❌

테스트 2

입력값 〉	["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]
기댓값 〉	"vinko"
실행 결과 〉	실행한 결괏값 "josipa"이 기댓값 "vinko"과 다릅니다.

테스트 3

입력값 〉	["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]
기댓값 〉	"mislav"
실행 결과 〉	실행한 결괏값 "stanko"이 기댓값 "mislav"과 다릅니다.
</aside>

결국 중복된 참여자가 있을 때, 이를 제대로 못 걸러내는 것을 확인할 수 있었다.

다시 1차 시도 때 제출했던 코드로 돌아가서, 테스트 2의 경우에 왜 vinko가 아닌 nikola가 나오는지 알아야 했다.

내 코드의 문제점은 completion 에서 원소의 값이 중간에 바뀌기 때문에 for문을 도는 과정에서 생략되는 경우가 발생하는 거였다.

• 리스트를 순회하면서 동시에 수정하기
  • for person in completion을 사용할 때, completion 리스트를 수정하면 순회 대상이 변경되어 의도한 결과를 얻을 수 없다.
  • 예를 들어, completion.remove(person)을 호출하면 리스트의 길이가 줄어들고, 다음 순회에서는 일부 요소가 건너뛰어질 수 있다.

그리고 생각을 해보니, 굳이 completion의 원소까지 삭제할 필요가 없었다. 따라서, 해당 코드를 삭제했다.

3차 시도

def solution(participant, completion):
    answer = ''
    for person in completion :
        if person in participant :
            participant.remove(person)
        else :
            continue
    answer = participant[0]
    
    return answer

코드 자체는 모든 테스트 케이스를 만족했으나, 효율성 문제가 발생하였다.

전부 ‘시간 초과’가 발생했다.. ㅠㅠ

participant 와 completion 을 일일히 비교해야했기에 문제가 발생하므로,

따라서, 미리 오름차순으로 정렬을 해준 뒤, 인덱스 값을 통해서 비교하는 방식으로 수정하였다.

👍🏻 최종 제출 코드

def solution(participant, completion):
    participant.sort() # 참가자 리스트 정렬
    completion.sort() # 완주자 리스트 정렬
    
    for p, c in zip(participant, completion): # 인덱스 값을 통해 비교
        if p != c: # 만약 완주하지 못한 참가자가 있다면,
            return p # 해당 값 반환 
    return participant[-1]  # 끝까지 차이가 없다면 마지막 사람이 미완주자

📝 새로 학습한 내용

사실 해당 코드는 ‘해시’를 이용한 풀이는 아니라고 생각됐다. 따라서, 다른 사람의 코드를 참고해보니, 각 종류당 해시 값은 모두 다르다는 점을 이용해서 참가자의 해시 값의 합에서 완주자의 해시 값의 합을 뺌으로써, 남은 최종 해시 값을 미완주자로 간주하는 방식이었다.

def solution(participant, completion):
    answer = ''
    temp = 0 # 참가자와 완주자의 해시 값을 더하고 뺀 남은 값
    dic = {} # 각 참가자의 해시 값을 key, 이름을 value로 저장하는 딕셔너리
    
    for part in participant:
        dic[hash(part)] = part # 각 참가자의 이름을 hase 함수를 통해 해시값으로 변환하고 dic에 저장
        temp += int(hash(part)) # 참가자들의 해시 값을 모두 더해 temp에 저장
    
    for com in completion:
        temp -= hash(com) # 참가자의 해시 값의 합에서 완주자의 해시값을 뺌
    answer = dic[temp] # 최종으로 남은 해시 값의 해당하는 value 값을 반환

    return answer

엄청 간결한 풀이는 이런 코드도 있었다.

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    # 참가자의 각 이름과 등장 횟수를 센 결과 - 완주자의 각 이름과 등장 횟수를 센 결과
    # 결국 participant에만 남아 있는 요소를 반환
    return list(answer.keys())[0] # 미완주자의 이름을 가져옴