완주하지 못한 선수 (hash)

kimki·2022년 4월 21일
0

코딩 테스트

목록 보기
1/1

완주하지 못한 선수

문제)

중복이 있는 participant 리스트와,
그보다 1만큼 적고 중복이 없는 completion 리스트가 주어질 때,
-> completion에 없는 participant를 구하라. ( 딱 1개 )

제출)

def solution(participant, completion):
    spar = sorted(participant)
    scom = sorted(completion)
    
    for i in range(len(scom)-1):
        temp1 = spar.pop()
        temp2 = scom.pop()
        if temp1 != temp2:
            return temp1
    # 정확성 테스트 2는 정렬했을 때, 마지막으로 participant 가 하나 남았을 때.
    # a a b b c // a b b c
    # a // 
    return spar.pop()

고민했지만, 구현하지 못한 내용

1. 내장 함수가 헷갈려서 print(dir(어떤_변수)) 로 조회함.

2. Hash를 이용해 조회시 O(1)이 되도록,

p_set = set(participant)
c_set = set(completion)
p_set - c_set 의 값을 return 하고 싶지만, participant는 중복이 있어서 불가.

3. Dictionary (HashMap)을 이용하면 한 쪽을 모두 담고, 카운트를 변화하거나 해당 Key의 Value를 빼는 식으로 저장하여 쓸 수 있겠지만, 결국 마지막에 찾기 위해 또 n번 만큼 조회해야 해서 사용 안함.


예시 답안

def solution(participant, completion):
    participant_set = set(participant)
    completion_set = set(completion)
    result = list(participant_set - completion_set)
    if result !=[]:
        return result[0]
    else:
        for c in completion:
            a=completion.count(c)
            b=participant.count(c)
            if(a != b):
                return c
    return None
    

2번의 내용에서 중복에 대한 것을, count(c)로 갯수를 세어 다른 경우 return 하였다.
나중에 중복을 만날 경우, "수" 로 비교가 가능하다는 것을 생각해보자.


Dictionary로 Hash를 이용한 풀이

O(1) 상수 시간의 접근을 위해 Hash Key를 사용하는 Dictionary 자료구조를 사용한다.

def solution(participant, completion):
	d = {}
    for x in participant:
    	# d.get(x) 를 한 값이 없으면 (Falsy 하면) 0을 넣고, 값이 있으면 1을 넣는다.
        d[x] = d.get(x, 0) + 1
        
    for x in completion:
    	d[x] -= 1
    
    # v가 0보다 큰, 즉 위의 completion 반복문에서 포함되지 않은 아이템의 key를 담는다.
    ans = [k for k, v in d.items() if v > 0]
    
    return ans[0]

알고리즘의 복잡도

순환문 1) participant 배열의 길이(n)만큼
순환문 2) completion 배열의 길이(n)만큼
ans =[ ... ] ) d의 길이(n)만큼.
-> linear time


.sort() 를 사용하면,
-> O(NlogN) 이 되므로 Hash를 사용한 풀이가 더 성능적으로 우수하다고 볼 수 있다.

profile
개발 자라는 사람.

0개의 댓글