• 출처 https://hsin.hr/coci/archive/2014_2015/contest2_tasks.pdf,
  프로그래머스

먼저 문제 설명을 하자면 도전자와 완주자가 있는데 도전자중 한명이 무조건 완주하지 못했다.

그 사람을 찾아라!

단순히 not in 으로 찾으면 안되는게 중복된 이름의 경우 찾기 힘들다.

정답코드 두개 보고 가자!

정석

def solution(participant, completion):
    answer = ''
    a, b = dict(), dict()
    completion.append('None')
    for i, j in zip(participant, completion):
        if i in a.keys():
            a[f'{i}'] += 1
        else:
            a[f'{i}'] = 1
        if j == 'None':
            break
        elif j in b.keys():
            b[f'{j}'] += 1
        else:
            b[f'{j}'] = 1
    for i in a:
        if i not in b or a[i] != b[i]:
            return i
    return answer

해쉬라는 것 자체가 메모리를 적게 사용해야 한다 최대 10만개의 리스트를 받기에 색인하는 리스트보다 딕셔너리가 훨씬 빠르다 아무리 for문이 여러번이라고 해도 리스트보다 빠르다.

일단 참가자와 경쟁자를 돌면서 딕셔너리를 만든다 중복값을 대비해서 이미있다면 +1 을 해주었다.

그후
참가자가 무조건적으로 완주자에 대해서 더 많은 정보가 있기에 참가자를 받아와서 완주자 딕셔너리에 있는지 또는 있다면 값이 같은지를 찾고 그렇다면 해당 참가자를 바로 return하게끔했다.

얍삽한 편법?

def solution2(participant, completion):
    participant.sort()
    completion.sort()
    for i, j in zip(participant, completion):
        if i != j:
            return i
    return participant[-1]

해당 요소가 편법인 이유는 해쉬, 즉 딕셔너리를 이용하지 않았기 때문이다.
sort로 요소를 똑같이 정렬하면 달라지는 지점이 있다. 없다면 마지막 요소가 다른 요소인 것이다.

그래서 달라지는 요소 부분의 참가자를 리턴한다.
꽤나 빠르다. sort는 속도가 오래걸림에도 꽤나 빠르다.