완주하지 못한 선수 (lv1)

 두 배열이 갖는 서로 다른 요소를 찾는 알고리즘이다. 두 배열은 각각 중복된 원소를 가질 수 있으며, 한 배열이 갖는 원소의 종류는 다른 배열이 갖는 원소의 종류에 종속된다.

 즉 중복된 원소를 찾고, 그 원소의 개수가 서로 다른 경우를 찾아내는것이 핵심이다. 생각해볼 수 있는 경우는 다음과 같을 것이다.

두 리스트 간 원소들을 직접 비교한다

 for문을 중첩해서, 말 그대로 index-value를 직접 비교하는 것이다. 이 경우 10^10 번의 연산이 필요해지기 때문에 사용할 수 없는 방법이다. 아래 그림을 참고해도, N의 범위가 100,000이기 때문에 O(N^2)은 사용하기 힘들다고 본다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

 딕셔너리를 이용한다

 for문을 중첩하여 돌리는 것을 포기했으니, 각 리스트에 대해 for를 한번씩 돌리면서, 혹은 다른 방법을 이용해 각 리스트를 딕셔너리로 변환한 뒤, 두번 이상 카운트된 원소(key값 으로 한다)들 끼리만 카운트 횟수를 비교하여 답을 구하는 방식이다.

dp = {}
dc = {}
for item in participant:
    try:
        dp[item] += 1
    except:
        dp[item] = 1
for item in completion:
    try:
        dc[item] += 1
    except:
        dc[item] = 1
for k,v in dp.items():
    if v >= 2 and v != dc[k]:
        answer = k

 위와 같이 딕셔너리 key값으로 이미 삽입된 리스트 원소는 추가로 카운트한 뒤, 다른 딕셔너리에 대해 비교 연산을 수행하면 된다. 연산량이 획기적으로 줄었으며, 정답으로 인정된 케이스이다.

---

리스트 내 중복 원소 찾기

파이썬 리스트 내 중복 원소만 추출/중복 제거 방법 정리 (tistory.com)

파이썬 리스트 내 중복 원소만 추출/중복 제거 방법 정리

sort() vs sorted()

[Python] sort( ), sorted( ) 차이 : 네이버 블로그 (naver.com)

[Python] sort( ), sorted( ) 차이

 sort는 원본 리스트를 직접 수정하고, sorted는 그렇지 않다.

리스트를 딕셔너리로 변환

[python] List to Dict (리스트를 딕셔너리로 변환) 총 정리!! (tistory.com)

[python] List to Dict (리스트를 딕셔너리로 변환) 총 정리!!

dictionary comprehension, fromkeys, 그리고 zip을 사용하는 방법이 있겠다.

Hashable 객체

[PYTHON] hashable 객체 : 네이버 블로그 (naver.com)

[PYTHON] hashable 객체

 hash 함수를 거쳐 숫자를 부여받은, immutable한 객체를 의미한다고 한다. 딕셔너리에서의 key값이나 set의 요소들 같이 중복되지 않는 값들이 예시이다.

Counter 객체

collections — Container datatypes — Python 3.10.5 documentation

collections — Container datatypes — Python 3.10.5 documentation

 dictionary 의 subclass이며, hashable 객체의 개수를 세는데 그 목적이 있다고 한다. 바꿔말하면, 같은 값을 같는 요소들의 개수를 세어 딕셔너리로 반환한다는 뜻이 되겠다. 아래와 같이 사용 가능하다. 또 중요한 점으로, Counter 객체 간에는 뺄샘, 덧샘이 적용된다.

c = Counter()                           # a new, empty counter
>>> c = Counter('gallahad')                 # a new counter from an iterable
>>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
>>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args

---

코드

from collections import Counter

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

 위 방법이 20ms 정도 더 빠르며, 작성도 간단하다.