끄적끄적
프로그래머스 lv1 [완주하지 못한 선수] C++, python - 해시 본문
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42576?language=python3
코딩테스트 연습 - 완주하지 못한 선수
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수
programmers.co.kr
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 반환
'코테준비' 카테고리의 다른 글
프로그래머스 level1 [모의고사] c++, python - 완전탐색 (0) | 2022.03.26 |
---|---|
프로그래머스 lv2 [전화번호 목록] C++, python - 해시 (0) | 2022.03.22 |
백준 2467 [용액] (0) | 2021.11.17 |
프로그래머스 lv2 [카펫] (0) | 2021.10.30 |
프로그래머스 lv2 [주식가격] (0) | 2021.10.30 |