[백준 문제풀이] 1920번 수 찾기(with. python)

1920번 문제는 간단한 수 찾기 문제이다.

시간 초과 에러

처음 문제를 풀고 채점 했을 때 시간 초과가 발생하였다. 원인을 찾아보니 list 때문이었다. list를 탐색하여 원소를 찾을 때, 순서가 있는 list의 특성 상 순차적으로 원소를 찾아가므로 최악의 시간 복잡도가 O(n)이 된다. 이 때문에 특정 케이스에서 시간 초과가 발생 할 수 있다.

해결

시간 초과 문제는 list 대신 set을 이용하여 문제를 풀면 해결된다. set은 순서가 없으며, 원소를 찾기위해 탐색할 때 시간 복잡도가 O(1)이기 때문에 list보다 탐색 시간이 짧다.

# N값 입력
input()

# N개의 수 입력 및 저장
arr1 = set(input().split())

# M값 입력
input()

# M개의 수 입력 및 저장
arr2 = input().split()

# 숫자 존재 유무 확인
for m in arr2:
    if m in arr1:
        print(1)
    else:
        print(0)

기타 사항

1. 첫 줄과 세 번째 줄에 주어지는 숫자 N과 M의 불필요
   • 이 문제에서 N과 M은 입력 받은 후 사용되지 않는다. 따라서 별도의 변수에 저장하지 않아도 된다.
2. 입력 받은 정수들을 string에서 int로 형변환 할 필요 없음
   • string 상태에서 집합 안에 존재하는지 확인 가능하기 때문에 굳이 map을 이용하여 형변환 할 필요가 없다.
3. 마지막에 입력 받는 정수들(M개의 수)는 별도의 변수 지정 불필요
4. if-else문을 한 줄로 바꿔 for문 안 코드 간소화

최종 코드

# N값 입력
input()
# N개의 수 입력 및 저장
arr = set(input().split())

# M값 입력
input()

# M개의 수 입력 및 존재 유무 확인
for m in input().split():
    print(1) if m in arr else print(0)