백준 - 수 찾기 1920

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

1920번: 수 찾기

문제 설명

- 아래 수열이 위에 있는 수열 속에 있으면 1, 없으면 0을 출력

 

코드 구상

이분탐색

1. 윗 수열을 정렬

2. left, right, pivot((left+right)/2) 값을 설정

3. left값이 right값보다 작거나 같을 동안 반복

  1) 값이 pivot보다 크면 left를 pivot+1로 옮김

  2) 값이 pivot보다 작으면 right를 pivot-1로 옮김

  3) 값이 pivot이랑 같으면 1을 출력하고 탈출하고 count를 1로 설정해줌

4. count가 0일 경우 0을 출력

 

코드

import sys

n = int(input()) #n입력받기
a_list = list(map(int, sys.stdin.readline().split())) #a수열 입력받기
m = int(input()) #m입력받기
m_list = list(map(int,sys.stdin.readline().split())) #m수열 입력받기
a_list.sort() #a수열 정렬

for i in m_list:
    count = 0
    left = 0
    right = n-1
    pivot = int((left + right)/2)
    while (left<=right):
        pivot = int((left + right)/2)
        if(a_list[pivot]<i): #중앙수보다 크면
            left = pivot+1
        elif(a_list[pivot]>i): #중앙수보다 작으면
            right = pivot-1
        else: #피벗이랑 같으면
            print(1)
            count = 1
            break
    if(count==0):
        print(0)