3. 백준 1920 (실버4) : 수 찾기 _ python풀이

* 문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

* 출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력 

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 

1
1
0
0
1

---

* 문제 해설

 이 문제는 알고리즘 분류 '자료구조'에 해당한다.

2번째로 푼 문제와 유사한 문제다. 다른 점은 이 문제에선 그 숫자가 존재하는지 유무만 확인하는 것이기 때문에 좀 더 쉽게 풀 수 있다고 생각했다. 마찬가지로 딕셔너리와 이분탐색을 이용해 부는 방법이 있을 것이라 생각했다.

 

 

* 나의 코드 

import sys

N=int(input())
N_s = list(map(int,sys.stdin.readline().split())) #시간초과를 우려해 input()사용안함
N_s.sort() #이분탐색 준비를 위한 정렬

M=int(input())
M_s = list(map(int,sys.stdin.readline().split()))

result = {}

def binarySearch(target, N_s): #이분탐색 함수
    start, end = 0, N - 1 #앞과 뒤
    
    
    while start<=end: #start가 end보다 커지기 전까지 반복
        mid = (start + end)//2 #중간값 갱신
        if target == N_s[mid]:
            return 1 # N_s에 값이 존재할 경우 1 리턴
        elif target < N_s[mid]:
            end = mid - 1
        else:
            start = mid + 1
        
    return 0 # 아예 찾지 못할 경우 0을 리턴

for target in M_s:
    result = binarySearch(target,N_s) # 이분탐색으로 각 요소가 존재하는지 여부 확인. 존재하면 1, 아니면 0
    print(result)

 

하지만 이 문제는 약간 달라 딕셔너리가 필요 없었고 순수하게 이분탐색으로 M_s의 요소가 N_s에 존재하는지 여부만 탐색하면 됐다. 이전에 풀었던 문제덕에 큰 어려움 없이 풀 수 있었던 문제였다.

 

 

 

*핵심 사항

이분탐색과 같은 알고리즘은 하나의 유형으로써 외워두면 문제풀이 시간을 단축할 수 있다.