[백준] 1920번 - 수 찾기

참고: https://www.acmicpc.net/problem/1920

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

문제에 대한 풀이를 생각해보면,

쉬운 것 같지만 자연수의 범위가 크기 때문에 고민해봐야한다.

 

import sys
input = sys.stdin.readline

n = int(input())
num = list(input().split())
m = int(input())
data = list(input().split())
    
for i in range(m):
    if data[i] in num: print(1)
    else: print(0)

 

수의 범위가 크지 않다면,

위의 코드로도 풀 수 있을 것이다.

 

하지만, N과 M 모두 10만까지의 경우의 수가 주어지고,

시간 제한이 1초로 되어있기 때문에 알고리즘 분류에 들어가는

정렬과 이분 탐색을 적용할 필요가 있다.

 

import sys
input = sys.stdin.readline

n = int(input())
num = list(input().split())
m = int(input())
data = list(input().split())
num.sort()

def bin_search(target, lists):
    start = 0
    end = len(lists)-1

    while start <= end:
        mid = (start+end) // 2
        if lists[mid] == target:
            return print(1)
        elif lists[mid] < target:
            start = mid+1
        else:
            end = mid-1
    
    return print(0)

for i in range(m):
    bin_search(data[i], num)

 

기본적으로 이분 탐색은 중간의 값 왼쪽과 오른쪽으로

나누어 탐색하는데, 타겟팅된 값이 중간이 아니라면

값을 더하거나 빼어 탐색하는 과정을 거친다.

그리고 타겟이 된 값을 탐색하는 리스트는 정렬되어 있어야하기 때문에

기존에 주어지는 num 리스트는 정렬해야한다.

 

화이팅 💪