[Python3] 백준(Baekjoon) 숫자카드2 10816

문제 :

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

접근 :

count를 통해서 풀어보려고 했는데 시간초과가 나왔고,

연속하는 숫자를 세기 위해서 while 문을 추가로 만들어서 s(start)와 e(end)라는 투포인터를 만들어서 문제를 풀어봤다. 하지만 또 시간초과가 나왔다.

그래서 결국 문제에 대한 풀이를 찾아봤고, 파이썬 내장 모듈인 bisect에 대해서 알게 되었다.

 

bisect는 파이썬에 내장되어있는 이진탐색 모듈이다.

bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스,

bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 인덱스를 알려준다.

 

풀이 :

#시간 초과 코드

from sys import stdin

def binary_serch(array, target, start, end):
    while start <= end :
        mid = (start + end) //2 
        if array[mid] == target : 
            s, e = 1, 1
            while mid - s >= start:
                if array[mid-s] != target:
                    break
                else :
                    s += 1
            while mid + e <= end:
                if array[mid + e] != target:
                    break
                else :
                    e += 1
            return s + e - 1
        elif array[mid] > target :
            end = mid - 1
        else :
            start = mid + 1
    
    return None

N = int(stdin.readline())
card = sorted(list(map(int, stdin.readline().split())))
M = int(stdin.readline())
tar = list(map(int, input().split()))
ans = []
for i in tar :
    result = binary_serch(card, i, 0, N-1)
    if result == None:
        ans.append(0)
    else :
        ans.append(result)
print(*ans, end=' ')

from bisect import bisect_left, bisect_right
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))
card.sort()

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


for i in range(len(test)):
    print(count_by_range(card, test[i], test[i]), end=' ')