Step 1: 해시(Hash) 대표 문제 풀이: 완주하지 못한 선수

---

알고리즘

문제 분석

문제 설명

최대 입력값이 10만으로 시간 복잡도가 O(N) 이나 O(NlogN) 정도인 알고리즘이 필요

제한사항

동명이인이 없다면 차집합으로 해결할 수 있겠지만 해당 조건이 존재하므로 다른 풀이가 필요

입출력 예

이름에 대해 얼마나 등장했는지 수를 파악

알고리즘 고안

자료구조(와 알고리즘)의 선택

• 만약이름 대신 번호가 주어졌다면

  • 선형 배열(linear array)을 이용하여 해결

• 번호 말고 다른 것(ex: str)로 접근 할 수 있는 자료구조는 없는가?

  • 해시를 이용

필요 개념

해시(hash)

해시 충돌(hash collision)

문제 풀이

예제를 통해 문제 풀이의 흐름을 익힌다.

participant	completion	return
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

1. part 배열을 살펴보며 hasg 테이블에 등록

   mislav	2
   stanko	1
   ana	1

2. com 배열에 있는 이름을 hash 테이블에서 제거

   mislav	1
   stanko	0
   ana	0

3. hash 테이블에 0이 아닌 key 값을 반환
   mislav

---

python 언어를 이용한 풀이

Dictionary 변수를 이용한 풀이

• python 에서는 dictionary 구현할때 내부적으로 해시를 이용하기 때문에 dictionary의 원소들을 해시를 이용하여 O(1) 시간에 접근 가능

def solution(participant, completion):
    dict = {}
    for name in participant:
        dict[name] = dict.get(name,0) + 1
        
    for name in completion:
        dict[name] -= 1
        
    dnf = [k for k, v in dict.items() if v>0]   
    
    answer = dnf[0]
    return answer

1. 해시에 접근 하는데 필요한 시간은 O(1) 이므로
   참가자를 계산할 때 O(N)의 시간복잡도를 가짐

2. 해시에 접근 하는데 필요한 시간은 O(1) 이므로
   완주자를 제외할 때 O(N)의 시간복잡도를 가짐

3. 완주하지 못한 선수를 찾을 때 O(N)의 시간 복잡도를 가짐

   이런 이유로 해당 함수의 시간복잡도는 participant 배열의 길이에 비례하는 linear time 알고리즘이라 할수 있음

배열의 정렬을 이용한 풀이

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

1. participant 배열을 정렬하는데 O(NlogN)의 시간 복잡도를 가짐
2. completion 배열을 정렬하는데 O(NlogN)의 시간 복잡도를 가짐
3. 두 배열을 0번지부터 원소를 비교 하는데 O(N)의 시간 복잡도를 가짐

이런 이유로 해당 코드에서 sort 함수는 O(NlogN) 복잡도를 가짐

---