https://www.acmicpc.net/problem/10816
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
> 이분 탐색 활용
탐색하는데 사용되는 시간효율성을 위해 이분탐색방법을 활용하였다. 기본 이분 탐색 개념에 중복되는 수의 개수를 카운트하는 아이디어만 생각할 수 있다면 풀 수 있는 문제였다.
먼저 입력값들을 받아오고 가지고 있는 카드들의 개수 정보를 담은 딕셔너리를 선언한다.
기본 이분 탐색 알고리즘에 중간값이 타겟과 같은 수 일 때 반환하는 값부분만 수정해주었다. 7 라인에서 딕셔너리에 저장되어있는 target의 개수부분을 반환하여 출력한다.
num이 lst에 없다면 None이 반환되기 때문에 17-20줄에 None대신 0으로 출력되도록 코드를 작성해주었다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 | 파이썬3] 1932. 정수삼각형 (0) | 2021.08.02 |
|---|---|
| [백준 | 파이썬3] 2164. 카드2 - 큐 (0) | 2021.08.02 |
| [백준 | 파이썬3] 2751. 수정렬하기2- 정렬 (0) | 2021.07.31 |
| [백준 | 파이썬3] 10773. 제로 - 스택 (0) | 2021.07.31 |
| [백준 | 파이썬3] 2606. 바이러스- dfs (0) | 2021.07.28 |