[Baekjoon] 10816번 : 숫자 카드 2 (Python, 이분 탐색)

[Baekjoon] 10816번 : 숫자 카드 2 (Python, 이분 탐색)

 

목차

 

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

Python

 

방법 1 - 메모리 112712KB / 시간 4288ms / 코드 길이 530B

 

1920문제에서 count 요소를 추가한 문제이다.

https://aigong.tistory.com/393

[Baekjoon] 1920번 : 수 찾기 (Python, 이분 탐색)

 

빠른 숫자 계산을 위한 이진 탐색을 설계한다. 단, 해당 target에 따른 개수를 찾기 위한 dict를 추가로 구성한다.

 

 

def bs(l, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if l[mid] == target:
        return cnt.get(target)
    elif l[mid] > target:
        return bs(l, target, start, mid-1)
    else:
        return bs(l, target, mid+1, end)

n = int(input())
a = sorted(list(map(int, input().split())))
m = int(input())
b = list(map(int, input().split()))

cnt = {}
for i in a:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

for i in b:
    print(bs(a, i, 0, len(a)-1), end=' ')

 

방법 2 - 메모리 112688KB / 시간 1016ms / 코드 길이 298B

 

Python은 정렬을 진행함에 있어 빠르게 진행하는 것이 각 함수에 내장되어 있다.

고로 단순히 dict에 개수를 저장해놓고 key에 대한 것이 존재하면 개수를 반환하고 그 외에는 0을 반환하는 방법으로 결과를 도출할 수 있다. 

 

n = int(input())
a = sorted(list(map(int, input().split())))
m = int(input())
b = list(map(int, input().split()))

cnt = {}
for i in a:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

for i in b:
    if i in cnt:
        print(cnt[i], end=' ')
    else:
        print(0, end=' ')