프로그래머스 lv1 [완주하지 못한 선수] C++, python - 해시

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42576?language=python3 

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

vector로 풀이하는 방법과 해시로 풀이하는 방법이 있다.

 

map은 key와 value를 쌍으로 사용하는 자료구조

key를 이용하여 value를 찾는다.

해시를 사용하는 이유 : 접근 속도가 빠르다.

python의 경우 딕셔너리를 이용하여 풀면 된다.

 

벡터를 이용한 솔루션은 정렬을 사용하면 된다.

단점 : 정렬을 해야하므로 비용이 많이 든다.

 

<해시>

• unordered map

- c++ stl 중 하나

- map보다 더 빠른 탐색을 하기 위한 자료구조

- 해쉬테이블로 구현한 자료구조로 탐색 시간 복잡도 O(1)

* 한편 map은 binary search tree로 탐색 시간 복잡도 O(log n) 

- #include<unordered_map> 선언

- 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능 보임

- but, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수 있음

- index로 접근할 수 없고 iterator로 접근하여야 한다

- key : iter->first, value : iter->second

- 반복문 사용시 auto 활용

 

 

1. c++ vector

 

 

 

2. c++ hash

 

key -  name   ,   value - 값

for(string name : participant) 

participant 배열에 있는 값을 name이라는 변수에 순차적으로 대입한다는 의미

participant 배열을 돌며 name index에 있는 값을 1씩 증가시켜주고, completion 배열을 돌며 중복되는 값을 1씩 감소시킨다. 이렇게 하면 완주하지 못한 사람만 1이 됨.

 

 

3. python - dictionary

 

 

answer.get(i, 0)

i가 answer 딕셔너리 키에 속하지 않는다면 0 반환