https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
n = input()
n = set(list(map(lambda x : int(x) , input().split() )))
c = input()
c = list(map(lambda x : int(x) , input().split() ))
for i in c :
if i in n :
print(1)
else:
print(0)
사실 이 문제는 문제가 어렵다기 보다는 시간 복잡도를 줄이는 방법을 아는지가 중요한 문제다
아마 대부분은 n을 그냥 리스트로 받고 시간 초과가 나왔을텐데
리스트 대신 set을 이용하여 집합을 만들어주면 시간 복잡도가 O(n)이 아니라 O(1)에 가깝게 줄어든다
이유는 집합은 리스트와 다르게 순서를 보장하지 않기 때문이다
해당 문제에서는 값의 순서가 중요하지 않으니 집합을 사용해주면 된다
'코딩 > 백준' 카테고리의 다른 글
| 백준 14916번 거스름돈 파이썬 코드 + 풀이 (0) | 2023.11.09 |
|---|---|
| 백준 20300번 서강근육맨 반례 + 파이썬 코드 + 풀이 (1) | 2023.11.09 |
| 백준 2839번 설탕 배달 파이썬 코드+풀이 (0) | 2023.11.04 |
| 백준 1744번 수 묶기 파이썬 코드+ 풀이 (0) | 2023.11.04 |
| 백준 2579번 계단 오르기 파이썬 문제 풀이 + 팁 (1) | 2023.10.30 |