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

알고리즘 고득점 kit - 해시 - lv 1

 

문제분석

• 단 한명의 선수만 마라톤을 완주하지 못함
• 완주하지 못한 선수의 이름 return

 

코드 설계

• completion 의 값을 돌면서 확인
• 있으면 없애기 (하나만)
• participant 에 남아있는 이름 return

 

정답 코드

1차 - 실패 (시간초과)

def solution(participant, completion):
    for i in completion:
        participant.remove(i)
    answer = "".join(participant)
    return answer

 

2차

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    return participant[-1]

• 정렬 후 같은 index에 대한 값이 다르면 해당 참가자 return
• 마지막 인덱스까지 같다면 
• 마지막 사람이 완주하지 못한 것

 

다른 사람 코드 1

collections

import collections

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

• list(ans.keys())[0]
  • ans는 Counter의 객체로 내부적으로 dictionary처럼 동작
  • ans.keys() 는 Counter 객체에서 키들의 뷰를 반환
  • 이후 dict_keys 객체를 리스트로 변환
  • dict_keys는 리스트와 유사하나, 인덱싱이나 슬라이싱을 직접 지원하지 않으므로 list( )를 사용해 명시적으로 리스트로 변환한 뒤, [0]으로 리스트의 첫번째 요소인 첫 번째 키를 가져온다.

 

• collections.Counter :  요소들의 개수를 세는 데 사용된다. 리스트나 문자열과 같은 반복 가능한 객체에서 각 요소가 몇 번 등장했는지 쉽게 셀 수 있다.

import collections

lst = ['a', 'b', 'c', 'a', 'b', 'b']
cnt = collections.Counter(lst)
print(cnt)

# result : Counter({'b': 3, 'a': 2, 'c': 1})

 

다른 사람 코드 2

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

participant 리스트를 순회하면서:

• 각 선수의 해시값을 계산하여 딕셔너리 dic에 저장
  • dic[hash(part)] = part는 선수 이름 part의 해시값을 키로 하고, part를 값으로 저장
• 선수의 해시값을 temp에 더합니다.
  • 이로써 모든 선수의 해시값의 합이 temp에 저장됩니다.

completion 리스트를 순회하면서:

• 완주한 선수의 해시값을 temp에서 뺌
• 이렇게 하면, temp에는 완주하지 못한 선수의 해시값만 남게 됨

따라서 최종적으로 완주하지 못한 선수의 이름 반환

 

다른 사람 코드 3

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

 

다른 사람 코드 4

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c:
            return p
    return participant[-1]

 

 

2차 풀이 - 2024.11.24

1차 - 테스트는 통과했으나 효율성 실패 (시간초과)

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for c in completion : 
        participant.remove(c)
    return ''.join(participant)

 

2차

from collections import Counter

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

 

 

3차 - 25.03.26

해설 코드

def solution(participant, completion):
    answer = ''
    part = {}
    for i in participant:
        # 동명이 있다면
        if i in part:
            part[i] += 1 # 추가
        else:
            part[i] = 1 # 생성
    # 완주자들 체크
    for i in completion:
        part[i] -= 1
        if part[i] == 0:
            del part[i]

    return list(part)[0]