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

프로그래머스 코딩테스트 연습 : 완주하지 못한 선수

참가자와 완주자 명단이 있다. 1명을 제외하고 모두 완주하였다. 완주하지 못한 참가자를 반환하라.

# 오류코드

처음 읽자마자 완주자를 참가자와 비교한 후 완주자를 참가자 명단에서 없앤 후 참가자 명단에 남은 사람을 출력하면 된다고 생각했다.
결과는 맞았지만 효율성이 꽝이였다.
in 리스트는 결론적으로 배열을 다 돌기 때문에 for문을 도는 것과 같으므로 O(n^2)이 걸린다.

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

# 정답코드

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]

두 리스트를 정렬시킨 후 순서대로 매칭시켜 매칭되지 않는 참가자를 완주자가 아닌 것으로 판단한다. 이 코드는 효율성 검사까지 통과하였다. sort() 연산이 O(NlogN) 정도 걸리므로 O(NlogN)+O(NlogN)+O(N) => O(NlogN)이 걸린다.

이외에 collections과 Hash를 이용해 더 효율적인 코드들을 짠 사람들도 있었다. 이같은 경우 O(N) 정도 시간이 걸리므로 더 효율적이라고 할 수 있다.

*collections

import collections


def solution(participant, completion):
	# 완주자 명단에 없는 참가자만 반환
    answer = collections.Counter(participant) - collections.Counter(completion) 
    return list(answer.keys())[0]

*Hash

hash는 dictionary와 같은 개념인 것 같다. 차이점은 hash 개념자체가 암호화적 측면이 있기 때문에 hash를 붙이면 key값이 암호화된 임의의 숫자로 변환된다.

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