[백준] 10816번 : 숫자 카드2

문제

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

풀이

[백준] 10816번 : 숫자 카드2 🥈(실버 4)
🎯 36.885%
⏰ 걸린 시간 : 25분

• 알고리즘 유형 : [이진 탐색]

📌 [포인트]

0. 일치하는 값 찾고 좌우로 일치하는 것의 개수 어떻게 찾아낼 것인가?

✔️ [시간 초과 해결방법]
0. 처음 풀이의 경우 일치하는 mid값을 찾으면 왼쪽 오른쪽으로 while문을 돌려서 카운트 해주는 방식이에서 시간초과 발생
1. bisect 이진탐색 라이브러리로 해결
2. bisect_left 해당 값 맨왼쪽 인덱스 찾아줌
3. bisect_right 해당 값 맨오른쪽 인덱스 찾아줌

✨ bisect 이진탐색 인덱스 값 찾아주는거 유용하다.

코드(code)

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
N = int(input())
Nums = list(map(int, input().split()))
M = int(input())
#Guess : Nums에서 찾고자하는 값들
Guess = list(map(int, input().split()))

Nums.sort()
answer = []

for i in range(M):
    start = 0
    end = N-1
    cnt = 0
    while start <= end:
        mid = (start+end)//2
        if Guess[i] == Nums[mid]:
           #count해줄때 찾고자하는 값의 왼쪽 오른쪽인덱스 찾아서 빼주면 된다.
            cnt = bisect_right(Nums, Guess[i]) - bisect_left(Nums, Guess[i])
            break
        elif Guess[i] > Nums[mid]:
            start = mid+1
        elif Guess[i] < Nums[mid]:
            end = mid-1
    answer.append(cnt)
print(*answer)

회고

이진 탐색문제 좀 더 풀어보면서 익숙해질 필요가 있다.
bisect 이진탐색의 값이 왼쪽 오른쪽 index값을 찾아주는 라이브러리 좋은듯

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/Binary_Search/10816(%EC%88%AB%EC%9E%90%20%EC%B9%B4%EB%93%9C2).py