https://www.acmicpc.net/problem/10816
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
[오답] → 시간초과
문제를 보자마자 'count() 함수를 사용하면 되겠다' 하고 풀었는데 역시나 오답,,, 호락호락하지 않은 백준!!!
...
이 문제를 검색해보다가 bisect 라이브러리를 사용하신 블로거를 보았다.
파이썬에서 이진 탐색을 쉽게 구현할 수 있는 bisect 라이브러리는 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적이다.
[참고]
https://blog.naver.com/yjyj4700/222202051529
[파이썬] bisect 라이브러리
파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공해요.'정렬된 배열'...
blog.naver.com
[정답]
1. 이진 탐색을 수행할 함수 count를 정의한다. 매개변수 list, left_value, right_value를 받아 가장 왼쪽 인덱스를 반환할 bisect_right() 함수를 사용하여 right_index를, 가장 오른쪽 인덱스를 반환할 bisect_left() 함수를 사용하여 left_index를 정의한다. 그리고 값이 특정 범위에 속하는 원소의 개수인 right_index - left_index 를 return 한다.
2. 숫자 카드의 개수 N을 입력받는다. 숫자 카드를 입력받아 int형태로 리스트 card에 넣는다.
3. 몇 개 가지고 있는 숫자 카드인지 구해야 할 M을 입력받는다. 수를 입력받아 int형태로 리스트 c_list에 넣는다.
4. c_list로 for문을 돌면서 count(card,i,i)를 출력한다.
'알고리즘 공부 > 백준 > Python3' 카테고리의 다른 글
| [백준 파이썬] #2108: 통계학 (0) | 2021.01.21 |
|---|---|
| [백준 파이썬] #11292: 키 큰 사람 (0) | 2021.01.20 |
| [백준 파이썬] #10867: 중복 빼고 정렬하기 (0) | 2021.01.18 |
| [백준 파이썬] #1002: 터렛 (0) | 2021.01.17 |
| [백준 파이썬] #10814: 나이순 정렬 (0) | 2021.01.15 |
