[Baekjoon] 수 찾기: 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을 출력한다.

think

처음 봤을 때 막 어려운 문제는 아니라고 생각이 들었다.

먼저 set과 파이썬의 삼항연산자를 사용하면 될 것 같다.

set의 intersection을 이용해보자.

간단하게 set 정리

• set은 중복을 허용하지 않고 indexing을 허용하지 않는다.
• 교집합: a & b 혹은 a.intersecton(b)
• 합집합: a | b 혹은 a.union(b)
• 차집합: a - b 혹은 a.difference(b)

code

# 수 찾기
import sys
N = int(sys.stdin.readline())
listA = set(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
listB = list(map(int, sys.stdin.readline().split()))
tmp = set(listB)
setInter = set(listA & tmp)
for item in listB:
    print(1) if item in setInter else print(0)

==> 시간 초과

ㅎㅎ..시간 초과가 발생했다. ..너무 많은 함수 호출 때문인 것 같다.

# 수 찾기
import sys
N = int(sys.stdin.readline())
listA = set(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
listB = list(map(int, sys.stdin.readline().split()))
tmp = set(listB) #set() -> O(len(..))
setInter = listA & tmp # set 없애기
for item in listB:
    print(1) if item in setInter else print(0) # in: O(1)

set을 없애주니 통과..

파이썬 자료형 및 연산자의 시간 복잡도

https://chancoding.tistory.com/43

위의 블로그를 참고하였다.

위 문제를 이분 탐색과 set 자료형을 이용하여 풀었을 때의 시간 복잡도의 차이를 정리해두셨는데 도움이 되었다.

• list의 자료형의 경우 삽입, 제거, 탐색, 포함 여부 확인 모두 O(n) 에 해당하는 시간 복잡도를 갖는다.

• set과 dictionary는 삽입, 제거, 탐색, 포함여부확인 연산에 O(1)의 시간 복잡도를 가지고 있다.

  --> 탐색 및 확인: set. dictionary 이용

  ​ 순서 및 index 접근 : list 이용