프로그래머스 완주하지 못한 선수 해시 맵 사용 풀이 파이썬

 

프로그래머스 완주하지 못한 선수 해시 맵 사용 파이썬

 

완주하지 못한 선수 문제는 인자로 participant와 completion이 주어집니다. 참가자 중 단 한명의 선수만 완주하지 못하는데요, 완주하지 못한 선수를 찾아내야 합니다. 

 

 

문제 제약 조건은 다음과 같습니다.

• 참여선수는 1 ~ 10,000명
• participant - competion = 1
• 참가자 이름은 알파벳 20자 이하
• 참가자 중 동명이인 존재할 수 있음

문제의 핵심은 동명이인이 있다는 점입니다. 단순하게 문자열만 비교해서 문제를 풀 수 없습니다. 

 

해시 맵 사용 파이썬

 

이 문제가 요구하는 핵심 개념은 해시 맵입니다. key ~ value로 이루어진 자료구조를 통해서 선수들의 이름과 완주 여부를 체크해주어야 합니다. 

 

 

문제에서 요구하는 hash function은 python에서 dictionary를 사용합니다. 

문제 풀이 순서는 다음과 같습니다.

1. 선수들의 이름을 key로 하는 dictionary를 생성한다.
2. dictionary의 value를 0으로 초기화한다.
3. participant를 순회하면서 value를 증가시킨다.
4. completion를 순회하면서 value를 차감시킨다.
5. dictoinary를 순회하면서 value가 1인 녀석을 찾아내서 answer에 담아 return

 

python dictionary key value for loop 사용법

 

파이썬에서 dictionary 자료구조를 key와 value 두개의 값을 순회하기 위해서는 dictionary의 items() 메소드를 사용합니다. 

예를 들어 아래와 같은 딕셔너리가 있다고 하면, 

tempDict = {'a':1, 'b':2, 'c':3}

for key, value in tempDict.items():
    print('key is ' , key , '\n')
    print('value is ' , value , '\n')

결과값 입니다.

 

 

딕셔너리 순환을 사용해서 프로그래머스 완주하지 못한 선수 문제를 풀어봅니다. 

def solution(participant, completion):
    answer = ''
    
    # 딕셔너리 선언
    player = {}
    
    # 1차 초기화
    for item in participant:
        player[item] = 0
    
    # 참가자 집계
    for item in participant:
        player[item] += 1
    
    # 완주자 집게
    for item in completion:
        player[item] -= 1
        
    # 딕셔너리 순회    
    for key, value in player.items():
        if value == 1:
            answer = key
            
  
    return answer

 

 

시간복잡도는?

 

여기서 딕셔너리를 생성하고 배열을 순회하면서 완주하지 못한 선수를 찾아냈는데요, 총 4번의 for loop를 돌았습니다. 즉 시간복잡도는 O(N)에 수렴합니다. 

 

 

 

해시 맵을 사용하는 특성상 모든 딕셔너리에 key~value 쌍을 생성해야 되서 for loop가 많이 사용되었습니다. 

🚀️ 도움이 되셨다면 구독과 좋아요 부탁드립니다 👍️