BOJ/백준-10816-python
문제
풀이
- 이분 탐색(이진 탐색) 알고리즘으로 접근하였다.
- 입력 데이터와 탐색 범위가 매우 넓은 편이라
sys
라이브러리의readline
함수를 이용하여 입력 속도를 줄였다. - 이진 탐색을 구현하기 위해 탐색할
list
데이터를sort
한 뒤, 중복된 데이터의 개수를dict
으로 할당하였다. - 이후 해당 데이터가 있는지 없는지 이진 탐색으로 하나하나 요소를 확인해가며 체크한 뒤, true false를 반환하도록 구현하였다.
코드
# https://www.acmicpc.net/problem/10816
# boj, 10816: 숫자 카드 2, python3
import sys
input = sys.stdin.readline
def solve(array, target, start, end):
while start <= end:
mid = (start+end)//2
if array[mid] == target:
return True
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
if __name__ == '__main__':
n = int(input())
card_list = sorted(map(int, input().split()))
m = int(input())
sanggeun_list = list(map(int, input().split()))
duplicate_cnt = {}
result = [0] * m
for i in card_list:
if i not in duplicate_cnt:
duplicate_cnt[i] = 1
else:
duplicate_cnt[i] += 1
for x in range(len(sanggeun_list)):
if solve(card_list, sanggeun_list[x], 0, n-1):
result[x] = duplicate_cnt[sanggeun_list[x]]
print(*result)
결과
출처 & 깃허브
Author And Source
이 문제에 관하여(BOJ/백준-10816-python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cosmos/BOJ백준-10816-python3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)