[programmers] 완주하지 못한 선수 (Python)

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

코딩테스트 연습 - 완주하지 못한 선수

 

분류가 해시로 되어 있다.

해시는 Key-value쌍으로 데이터를 저장하는 자료구조라고 한다.

나는 해시를 몰랐기 때문에 아래와 같은 코드를 작성했지만 효율성에서 0점을 받았다 ㅎㅎ

def solution(participant, completion):
    answer = ''  
    for i in range(len(completion)):
        for j in range(len(participant)):
            if completion[i] == participant[j]:  # 같은 값이 있으면 
                del participant[j] 
                break
    answer = "".join(participant)  # 리스트를 문자열로 변환
    return answer

결국 계속 시도하다가 Googling을 해보았다..

 

그리고 새롭게 알게된 점

zip이 두 배열을 index로 묶어줄 수 있는 것은 알았지만, 길이 가 더 긴 배열을 잘라주는 기능을 하는지는 알지 못했다.

아래 코드의 로직은

• 두 리스트를 정렬한다.
• 정렬된 리스트를 zip으로 묶었을 때, 다른 값이 있다면 완주하지 못한 참여자이므로 return한다.
• 따로 없다면, zip으로 묶으면서 잘렸을 participant의 마지막 참여자이므로 pop()을 통해 return한다.

전체 코드

def solution(participant, completion):
    answer = ''  
    participant.sort()  # 정렬하고 시작
    completion.sort()
    for p, c in zip(participant, completion):  # p, c는 같은 index끼리 묶인 값
        if p != c:
            return p
    return participant.pop()  # 정렬하고 zip으로 묶어주었을 때 다른 것이 안나왔다면, 마지막 참여자가 다른 것(completion에 없는 것)이므로 pop을 통해 가장 최상단 값을 꺼내어 return한다.

다행히 정확도와 효율성에서 모두 통과를 하고 다른 사람의 풀이를 봐보니, 정말 간결해서 한 가지 더 추가했다.

 

아래의 코드에서는 Counter라는 컬렉션을 사용하여 간결하게 작성하였다.

Conuter란?
해시 가능한 객체를 세기 위한 dict 서브 클래스이다. 요소가 딕셔너리 키로 저장되고 개수가 딕셔너리값으로 저장되는 컬렉션이다.

예를 들면,

c = Counter(['eggs', 'potato'])

c['bacon']    // 0

c['eggs']      // 1

 

전체 코드

from collections import Counter

def solution(participant, completion):
    answer = Couner(participant) - Counter(completion)
    return list(answer.keys())[0]     # 한명이 완주하지 못하기 때문에 [0]으로 쉽게 return할 수 있다.

새로 알게된 점은 이 Counter도 dict라는 것이고,

Counter 객체는 뺄셈을 통해 서로 일치하는 값을 뺄 수 있다는 점. 이 기능 때문에 한 줄로 끝낼 수 있다.