[해시] 완주하지 못한 선수

 

https://programmers.co.kr/learn/courses/30/lessons/42576

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

 

해시를 모르고 풀었을 때의 코드

def solution(participant, completion):
    flag = 0;
    answer = ''
    com = completion
    for i in participant:
        flag = 1;
        for l in com:
            if i == l:
                flag = 0;
        if flag == 1:
            answer = i
            break
        com[com.index(i)] = "0"
            

        
            
    return answer

com = completion 은 사실 원본 리스트를 건드리기도 좀 그렇고 헷갈려서

(python이 오랜만이다...) 일단 그렇게 했다. '0' 처리도 없애는 법 기억 안 나서

효율성빵점

파이썬의 해시(Hash) = 딕셔너리(Dictionary)

해시 테이블로 구성되어있다고 함

딕셔너리 함수의 시간 복잡도는 O(1) 무척 빠름

 

def solution(participant, completion):
    part_dict = {}
    answer = ''
    
    for i in participant:
        part_dict[i] = part_dict.get(i,0) + 1
        
    for l in completion:
        part_dict[l] = part_dict.get(l,0) - 1
        
    for k in part_dict:
        if part_dict.get(k, 0) != 0:
            answer = k
            break
    
        
            
    return answer

1. participant로 딕셔너리를 만들었다. 그리고 각각의 값으로 1을 넣어주었다.

2. completion의 원소가 딕셔너리 part_dict에 있다면 1을 빼주었다.

3. 결론적으로 completion 리스트에 이름이 있다면 그 value는 0이 되어야 한다. (동명이인도 마찬가지. 만약 동명이인이 2명이라면 1을 수행하면서 2의 값을 가졌을것이다. 따라서 그 동명이인의 수 만큼 completion 리스트에 이름이 있어야지만 0이 된다. 결국엔 하나가 러닝에 성공했든 둘이 성공했든 계산엔 문제가 없다.)

4. 만약 0이 아닌 value를 가진 값이 있다면 그 값이 완주하지 못한 사람이다. 그리고 불필요한 연산을 피하기 위해 break해준다.

 

 

-진짜 이중 루프문이 확실히 시간 복잡도가 높아지는구나... 를 느꼈다.

 

 

 

참고한 글:

https://yunaaaas.tistory.com/46