[프로그래머스] 완주하지 못한 선수 - 리스트 정렬, 해시

내가 짠 코드

def solution(participant, completion):
	if len(completion) == 0:
        return participant
    
    else:
        for c in completion:
            participant.remove(c)

    return participant[0]

나름 깔끔하다 생각했지만 for문으로 인해 효율성 점수가 0점이 나왔다...

리스트의 원소제거를 어떻게 하면 더 빨리 할 수 있을까?

어떻게 짜야 빨리 탐색할 수 있을까?

풀이방법들

1. collections 사용

from collections import Counter
def solution(participant, completion):
    return list(Counter(participant) - Counter(completion))[0]

# collections의 Counter 함수는 리스트에서 원소의 개수를 각각 카운트해서 {원소: 갯수}의 형태를 가진 딕셔너리를 반환한다.

원래 다른 사람들의 코드에서는 collections만 import 한 뒤에 collections.Counter를 사용했지만, 나는 좀 더 깔끔하게 쓰고 싶어서 import를 제한했다.

알아둘 것: Counter의 collections 사용법, 각 객체 간에는 '-' 연산이 가능하다는 것!!

2. 딕셔너리와 hash함수 사용

hash(문자열)

해싱이란?

어떤 값을 해시함수에 넣어서 변환시켜주는 것... 일대일 대응관계이기 때문에 같은 input이면 해시 후의 결과는 항상 똑같다.

이런 식으로 각 선수들의 이름을 hash함수로 해싱하고, {해싱한 값 : 선수 이름}의 방식으로 참여자(participants) 딕셔너리를 만들었다. for 문으로 해싱을 하며 "키: 값" 을 넣어주면서 해싱한 값을 temp에 더해주었다.

그 뒤에는 완주자(completion)으로 똑같이 해싱을 하는데, 이미 선수들의 이름과 해싱값을 가진 딕셔너리가 완성되어있으므로 해싱한 값을 temp에서 빼주기만 했다. 결과적으로 나오는 것은 도달하지 못한 유일한 한 선수의 hash값이 나올 것이다. 이 값으로 딕셔너리[키]를 하여 마지막 선수를 알아냈다.

진짜 기발하다..

알아둘 것: hash함수가 있다는 것,,,,?

3. sort 사용

이게 그나마 내가 생각해낼만한 코드인 것 같다. 

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

사실 처음에는 

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

이런 식으로 작성했는데 이랬더니 NoneType은 len이 어쩌고 하면서 실행이 되지 않았다. 

TypeError: object of type 'NoneType' has no len()

리스트.sort()는 원본이 바뀐다. 

sorted(리스트)는 원본이 바뀌지 않는다.

 

정리

# 코드를 완전 간결하게 만들어주는 모듈 Counter
from collections import Counter

# 문자열을 해싱해주는 hash 함수
hash('문자열')

# 리스트 정렬하기
lst.sort() # 원본이 바뀐다.
sorted(lst) # 원본이 바뀌지 않고 정렬한 새로운 리스트를 반환한다.