[Algorithm] 프로그래머스 완주하지 못한 선수(해시)

문제

 

 

 해당 문제는 해시 알고리즘으로 분류된 문제이며,

 

겉으로 봤을 땐 단순히 participant 내에 있는 원소 중 completion 에 존재하지 않는 원소가 있다면,

 

즉 참가자 이름에는 있지만 완주자 리스트에는 없는 이름을 리턴하면 되는 문제이다.

 

처음 풀이

 

  단순히 문제를 보자마자 리스트 원소 존재 유무에 따라서 다음과 같이 코드를 작성하고 채점을 했더니,

 

효율성 부분에서 시간초과가 떴다.

 

def solution(participant, completion):
    answer = ''
    
    for i in participant:
        if i in completion:
            completion.remove(i)
        else:
            answer = i
    return answer

 

 

다른 풀이 1 - 정렬 후 비교

 

  -  리스트 내의 모든 원소를 하나씩 비교하는 것은 시간 효율이 매우 떨어지기 때문에, 

 

  -  두 리스트를 정렬하면, 완주한 선수의 경우 participant 리스트와 completion 리스트 내에 동일한 인덱스에 위치할 것이다.

 

  -  문제에서 완지하지 못한 선수는 단 한 명이라고 했으니! 

 

  -  따라서, 각 리스트 원소 중 동일한 위치(인덱스)에 동일한 원소가 존재하지 않는다면, 

 

    즉, participant 에 한 명의 선수가 더 존재하는 거라면 해당 선수가 완주하지 못한 선수라는 것이다.

 

  -  따라서 두 리스트 원소를 비교하다가 같은 위치의 원소가 다를 경우 해당 원소를 리턴하면 되는 것이다.

 

  -  만약, completion 기준으로 리스트 원소를 다 돌았는 데에도 리턴되는 값이 없다면, participant 의 마지막 원소가 완주하지 못한 선수일 것

 

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

 

다른 풀이 2 - Collections.Counter 객체 사용

 

  -  정말 똑똑한 사람들,, python 의 정말 간결성을 그대로 가져갈 수 있는 풀이가 아닐까 싶다. 

 

  -  해시 처리할 때 collections.Counter 사용!!!!!! 

from collections import Counter
def solution(participant, completion):
    answer = ''

    answer = (Counter(participant) - Counter(completion)).keys()
    answer = list(answer)[0]

    return answer

 

    collections.Counter() 는 산술/집합 연산이 가능하다.

 

    1.  덧셈 연산

 

from collections import Counter

counter1 = Counter("I study hard")
counter2 = Counter(['I', 's', 't', 'u', 'd', 'y', 'm' , 'a',' t', 'h'])
print('counter1 : ', counter1)
print('counter2 : ', counter2)
print('counter1 + counter2 : ', counter1 + counter2)

counter1 :  Counter({' ': 2, 'd': 2, 'I': 1, 's': 1, 't': 1, 'u': 1, 'y': 1, 'h': 1, 'a': 1, 'r': 1})
counter2 :  Counter({'I': 1, 's': 1, 't': 1, 'u': 1, 'd': 1, 'y': 1, 'm': 1, 'a': 1, ' t': 1, 'h': 1})
counter1 + counter2 :  Counter({'d': 3, 'I': 2, ' ': 2, 's': 2, 't': 2, 'u': 2, 'y': 2, 'h': 2, 'a': 2, 'r': 
1, 'm': 1, ' t': 1})

 

    2.  뺄셈 연산

 

from collections import Counter

counter1 = Counter("I study hard")
counter2 = Counter(['I', 's', 't', 'u', 'd', 'y', 'm' , 'a',' t', 'h'])
print('counter1 : ', counter1)
print('counter2 : ', counter2)
print('counter1 - counter2 : ', counter1 - counter2)

counter1 :  Counter({' ': 2, 'd': 2, 'I': 1, 's': 1, 't': 1, 'u': 1, 'y': 1, 'h': 1, 'a': 1, 'r': 1})
counter2 :  Counter({'I': 1, 's': 1, 't': 1, 'u': 1, 'd': 1, 'y': 1, 'm': 1, 'a': 1, ' t': 1, 'h': 1})
counter1 - counter2 :  Counter({' ': 2, 'd': 1, 'r': 1})

 

  -  공백도  포함되어서 나오는 것을 확인할 수 있다.

 

 

    3.  교집합(&), 합집합(|) 연산

 

from collections import Counter

counter1 = Counter("AAABBBCCCDDD")
counter2 = Counter("ABCDEFG")

print('counter1 & counter2 : ', counter1 & counter2)   # 교집합
print('counter1 | counter2 : ', counter1 | counter2)   # 합집합

counter1 & counter2 :  Counter({'A': 1, 'B': 1, 'C': 1, 'D': 1})
counter1 | counter2 :  Counter({'A': 3, 'B': 3, 'C': 3, 'D': 3, 'E': 1, 'F': 1, 'G': 1})

 

 

다른 풀이 3 - 해시 함수

 

  -  participant 의 각 원소를 돌면서, 각 원소 별로 hash() 를 처리해 해시 키를 만들어 딕셔너리의 key 값으로 하고

 

  -  tmp 라는 변수에 participant 를 돌면서 만들 해시 키값을 계속해서 추가한다.

 

  -  completion 의 각 원소를 돌면서 completion의 각 원소 별로도 hash() 함수를 처리하여 해시 키를 만드는데, 

 

    이때 participant 반복문을 돌면서 생성한 해시 키 값을 추가했던 tmp 에서, completion 의 각 원소를 돌면서 만든 해시 키 값을 빼준다.

 

  -  그러면, 마지막으로 남은 tmp 는 participant 에는 존재하지만 completion 에는 존재하지 않는 원소의 해시 키인 것이다.

 

  -  따라서, 딕셔너리에서 해당 해시 키에 대응되는 값을 리턴하면 되는 것이다.

 

  -  이렇게 문제를 풀어본 적이 없었는데,, 많이 배웠다 진짜ㅠㅠㅠㅠㅠ

 

def solution(participant, completion):
    answer = ''
    
    tmp = 0
    dic = dict()
    for i in participant:
        dic[hash(i)] = i
        tmp += hash(i)
        
    for j in completion:
        tmp -= hash(j)
    
    answer = dic[tmp]

    return answer

 

딕셔너리와 리스트 시간 복잡도 차이

 

연산	Dictionary	List
Get	O(1)	O(1)
Insert	O(1)	O(1) ~ O(N)
Update	O(1)	O(1)
Delete	O(1)	O(1) ~ O(N)
Search	O(1)	O(N)

 

 

참고

 

  -  https://velog.io/@kimdukbae/Python-collections-%EB%AA%A8%EB%93%88%EC%9D%98-Counter

  -  https://yunaaaas.tistory.com/46

  -  해시 테이블 참고 : https://velog.io/@inyong_pang/%ED%95%B4%EC%89%AC-%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table