[알고리즘] 백준 1920 (파이썬 풀이)

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

1920번: 수 찾기

문제

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을 출력한다.

 

해결코드

실패코드-1

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
li = []
for i in range(m):
    if(b[i] in a):
        li.append('1')
    else:
        li.append('0')
print("\n".join(li))

문제를 보자마자 그냥 in 함수 쓰면 풀리겠구나 싶어서 제출했으나.. 당연하게도 시간초과가 떠버렸다.

문제 밑에 알고리즘 분류를 보고 이분탐색으로 풀어야겠다는 생각이 들었다.

 

성공코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
m = int(input())
b = list(map(int, sys.stdin.readline().split()))
li = []

for i in range(m):
    cnt = False
    left = 0
    right = n-1
    while(left<=right):
        mid = (left+right)//2
        if(a[mid] == b[i]):
            cnt = True
            break
        elif(a[mid] < b[i]):
            left = mid+1
        else:
            right = mid-1
    if(cnt == True):
        li.append('1')
    else:
        li.append('0')
print("\n".join(li))

 

문제풀이

입력시간을 최대한 줄이기 위해 sys 라이브러리의 readline을 사용하여 입력받는다.

차례대로 n,a,m,b를 입력받아준다. (a,b는 리스트에 담아준다)

결과값을 담아줄 li를 하나 생성한다.

for문을 돌리는데 m만큼 반복해줘야한다.

이 문제는 이분탐색을 이용하여 풀어야하므로 left, right값을 선언하고 cnt값을 초기에 False로 초기화한다.

그 밑에 while문을 돌린다.(left값이 right보다 작거나 같으면 계속 반복)

mid값은 left값과 right값을 더해서 2로 나눈 자연수 몫이다.

만약 a[mid]와 b[i]가 같다면 cnt값을 True로 바꾸고 while문을 빠져나온다.

a[mid]값이 더 작다면 left값을 mid에 +1한 값으로 바꿔준다.(중간부터 맨끝까지 탐색)

a[mid]값이 더 크다면 right값을 mid에 -1한 값으로 바꿔준다.(처음부터 중간까지 탐색)

이걸 계속 반복하다 보면 left값이 right값보다 커지는 시점이 올텐데 그 때 while문을 종료한다.

while문을 종료할 때 cnt값이 True이면 li에 '1'을 추가하고 cnt값이 False라면 li에 '0'을 추가한다.

한 줄에 한 개씩 출력해야 하므로 print("\n".join(li))으로 결과값을 출력해준다.