[🐙 알고리즘] 프로그래머스 lv.1- 완주하지 못한 선수 / Python

https://school.programmers.co.kr/learn/courses/30/lessons/42576

문제

---

풀이

def solution(participant, completion):
    d = dict()

    for person in participant:
        if person not in d:
            d[person] = 1
        else:
            d[person] += 1

    for c in completion:
        if c in d:  
            d[c] -= 1

    for person in d.keys(): 
        if d.get(person) == 1:
            return person  

풀이과정

1. dict로 딕셔너리를 생성한다. (바로 { } 로 작성하는 것도 가능하다.)
2. participant 배열을 순회하며 딕셔너리에 1로 초기화, 이미 딕셔너리에 존재하는 경우에는 +1
3. completion 배열을 순회하며 해당 값이 있는 경우에는 딕셔너리의 값을 -1
4. 2-3의 과정을 통해서 동명이인의 경우 또한 필터링 가능하다.
5. 마지막으로 completion 배열에 존재하지 않는 사람은 1값을 가지므로 그 사람이 결과값이 된다.

---

딕셔너리 구조를 사용하는 이유 -> 시간 단축!

위 문제는 해시를 사용하여 풀라고 알려주는 문제였다.

위 문제는 해시를 사용하지 않고도 쉽게 구현이 가능하지만,
효율성에서 통과되지 않아서 딕셔너리 구조를 사용해보기로 했다.

파이썬에서 해시를 구현하기 위해서는 파이썬의 딕셔너리를 사용하면 된다.

딕셔너리 구조를 쓰면 아래와 같은 장점이 있다고 한다.

1. 리스트를 쓸 수 없을 때
   -> 문자 인덱스처럼 사용하고 싶은 경우
2. 빠른 접근 / 탐색이 필요할 때
   -> 딕셔너리 함수의 시간복잡도는 대부분 O(1)로 매우 빠름
3. 집계가 필요할 때
   -> count메서드를 사용, 원소의 개수를 세는 문제에서 유리

---

참고하면 좋은 딕셔너리 관련 메서드

dict = {'park':1,'kim':2,'Baek':3}

print(dict.keys()) # dict_keys(['park', 'kim', 'Baek'])
print(dict.values()) # dict_values([1, 2, 3])
print(dict.get('park')) # 1

dict.keys() - 딕셔너리의 키들을 반환
dict.values() - 딕셔너리의 키의 값들을 반환
dict.get(찾고자하는 키) - 해당 키의 값을 반환

---

참고하면 좋은 블로그!
https://yunaaaas.tistory.com/46