백준 1920

<원하는 정수 찾기> 문제

난이도 : 실버 4

1. 백준 문제
   링크텍스트

2. 코드 알고리즘
   

3. 코드

#1920
#https://www.acmicpc.net/problem/1920

import sys

input = sys.stdin.readline

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

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

a.sort()
#우린 지금 median으로 target을 찾아내려 하는 것
for i in range(m):
    target = b[i]
    start = 0
    end = n-1
    check = 0 #한번도 못찾은 경우
    while (start<=end): #한번도 없는 예외 경우 제외
        #또 여러개 있을 경우 여러번 세리도록
        #while문에서만 target을 찾음/ for문은 다음 target
        median = int((start+end)/2)
        if (a[median] > target):
            end = median - 1
        elif (a[median] < target):
            start = median + 1
        else:
            check += 1 #여러번 찾을 수도 있으므로
            break
    print(check)

4. 후기

   이진 탐색의 의미를 제대로 이해할 수 있었던 문제...
   그냥 median 값을 반 씩 줄여나가면 되는 줄 알았는데
   start과 end를 조정하면서 median값을 target과 일치하는 지 확인해야 됐던 것!

   처음에 start과 end도 조정해줘야 되나? 라고 생각만 했는데
   코딩은 항상 오버가 없다... 항상 최선을 다하자! 중첩안될시 무조건 고려하자