백준 1920번 - 수 찾기 / Python

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

 

---

정답

import sys

input = sys.stdin.readline

n = input()
a = set(input().split())
m = input()
b = input().split()

answer = ''
for i in b:
    answer += '1\n' if i in a else '0\n'

print(answer)

---

풀이

 숫자를 입력받아 배열에 있는지 찾는 문제입니다. 처음에는 알고리즘 분류가 이분 탐색으로 되어있어 binary search 를 이용하여 문제를 풀었습니다.

 

import sys

input = sys.stdin.readline

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


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return True
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return False


answer = ''
for i in b:
    if binary_search(a, i, 0, n - 1):
        answer += '1\n'
    else:
        answer += '0\n'

print(answer)

 이분 탐색으로 풀게되면 시간이 608ms나 걸리게 됩니다.

 

 그래서 다른 사람들의 코드를 보니 set을 이용하여 풀면 매우 빠르게 해결이 되는 것을 보고 set을 이용하는 것으로 변경했습니다. set은 해쉬를 이용하여 탐색을 하기 때문에 상수 시간으로 탐색을 할 수 있으며, 다른 값과 비교를 하는 것이 아니기에 int로 변환할 필요 없이 str 타입으로 그대로 사용하면 됩니다.