백준 10816번
숫자 카드 2
이분탐색, binary search
PYTHON
어떤 리스트 안에 내가 원하는 숫자가 몇 개 들어있는지 그 개수를 세서 출력하는 문제이다.
하지만 시간 제한이 있고, 숫자의 범위가 큰 만큼 효율적인 알고리즘을 통해 해결해야 한다.
시간 초과 코드
일반적인 이분 탐색 알고리즘이다 근데 이제 count 함수를 곁들인.
이 문제는 이렇듯 일반적인 이분 탐색 알고리즘을 통해서는 해결할 수 없다.
아래에서 두 가지 방식을 제안한다.
해쉬 함수
파이썬에는 해쉬 함수의 형식을 띄는 dictionary, 사전 이 존재한다.
이 딕셔너리를 이용해 리스트를 탐색하면서 나온 숫자를 카운트하고 이를 딕셔너리 값으로 입력한다.
이 과정을 예시로 살펴본다.
만약 리스트가 10 2 3 10 이라고 할 때, 딕셔너리는 탐색에 따라 아래와 같이 변한다.
{} => {10: 1} => {10:1, 2:1} => {10:1, 2:1, 3:1} => {10:2, 2:1, 3:1}
이렇게 모든 숫자의 등장을 세고 나면 우리가 궁금한 숫자의 리스트를 순차대로 딕셔너리에서 검색한다.
이 과정이 마지막 포문이다.
Counter 함수
Counter 함수는 리스트 내부의 원소의 개수를 세서 딕셔너리 형태로 만들어주는 함수이다.
Counter 함수를 사용했을 때, 저장되는 값은 아래와 같다.
그 외에 출력을 하는 과정은 문법은 다르지만 위의 소스 코드와 정확히 동일하다.
Counter 함수 사용 예시 
Whiplash We Flash