[프로그래머스 코딩테스트 고득점 Kit / 해시] 완주하지 못한 선수 (python)

풀이

def solution(participant, completion):
    answer = ''
    cDic = {}
    
    for i in completion:
        if i in cDic:
            cDic[i] += 1
        else:
            cDic[i] = 1
        
    for i in participant:
        if i in cDic:
            cDic[i] -= 1
            
            if cDic[i] == 0:
                del cDic[i]
            
        else:
            answer = i
            break
    

    
    return answer

배열로 풀었다가 효율성 테스트 때문에 애먹은 문제.

 

• 딕셔너리를 사용해서 풀었다. 딕셔너리는 해시를 사용하기 때문에 검색 시간복잡도가 O(1)이다.
• 딕셔너리는 d1 = {} 또는 d1 = dict() 으로 선언한다.
• 우선 completion 리스트의 각 값을 key로 해서 딕셔너리를 생성했다. 이때 value는 completion 안에 key 값이 몇 개있는지를 적었다.
• 그리고 participant를 반복문을 돌면서 딕셔너리 안에 있는지 확인하고, 없으면 그게 정답이다.
• 딕셔너리 안에 있다면 value 값을 -1해주고, 만약 0이되면 더이상 없다는 뜻이므로 딕셔너리에서 삭제한다.

 

Python Dictionary 기능 정리

1. 선언
   • dict1 = {}
   • dict1 = dict()
2. 접근
   • dict1[key]            # value 접근, 키 값 없으면 오류남
   • dict1.get(key)      # value 접근 키 값 없어도 오류 안남
   • dict1.keys()          #딕셔너리 내 모든 key를 반환
   • dict1.values()       #딕셔너리 내 모든 value를 반환
   • dict1.items()         #딕서너리 내 모든 key와 value 쌍을 반환 (반환 값은 리스트나 튜플이 아님)
3. 삭제
   • del dict1[key]
   • dict1.pop(key)       #value를 반환하면서 삭제
4. 삽입
   
   • dict1[key] = value
   • dict1.update(dict2)
   • dict1.setdefault(key, value)
   • dict1 = dict.fromkeys([key1, key2, key3, ...], defalut)                                                                                          #key 리스트에 default값을 value로 짝지어서 딕셔너리를 생성