백준 1920번 - 수찾기 (파이썬/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을 출력한다.

답안

T_1 = int(input())
lst_1 = set(list(map(int, input().split())))        # lst_1은 중복을 제거해서 불필요한 과정을 줄여야한다.

T_2 = int(input())
lst_2 = list(map(int, input().split()))

for i in lst_2:                                     # lst_2를 순회해서 i가 lst_1에 있으면 1출력, 없으면 0출력
    if i in lst_1:
        print(1)
    else:
        print(0)

후기

점점 시간복잡도를 신경써야 하는 문제들이 나오기 시작했다.

시간안에 문제를 해결하기 위해서는 for문을 줄이고, 중복된 값을 제거해 불필요한 연산을 피해야 한다.