[백준] #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을 출력한다.

예제 입력

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

예제 출력

1
1
0
0
1

백준 1920번 문제

💡Idea

파이썬의 자료구조를 잘 활용해서 시간복잡도를 낮추는 것이 관건인 문제라고 생각했습니다.

A의 수들을 리스트로 만들고, 입력받은 M개의 각각의 수들이 리스트 내에 하나씩 있는지 확인하면 시간 초과가 납니다.

따라서, 리스트가 아닌 set나 dictionary를 사용하여 문제를 해결할 수 있다고 생각했습니다.

⏰in 연산자 사용시 시간복잡도

• list, tuple : 요소 하나씩 순회 검색을 하기 때문에, $O(n)$의 시간복잡도를 가집니다.

• set, dictionary : 내부적으로 해시를 통해 값을 저장하기 때문에, $O(1)$의 시간복잡도를 가집니다.
  다만, 충돌이 많아 해시의 성능이 떨어지는 경우에는 $O(n)$의 시간복잡도를 가질 수 있습니다.

💻코드

import sys
input = sys.stdin.readline

N = int(input())
A = set()
for a in list(map(int, input().split())):
    A.add(a)

M = int(input())
for a in list(map(int, input().split())):
    print(1) if a in A else print(0)

📝코드 설명

변수

• N : A의 길이
• A : 주어진 수들이 포함되어 있는지 확인하는 기준 리스트
• M : 포함 여부를 확인해야 하는 수들의 길이

주어진 N개의 수들을 set로 만들어 저장합니다.

그리고, M개의 수들이 집합에 포함되어 있는지 반복문을 돌며 각 요소 별로 확인하여, 포함되어 있다면 1을, 그렇지 않다면 0을 출력하도록 합니다.

Reference

파이썬 'in' 연산자 시간복잡도