백준 1920번 문제 바로가기

첫 번째 시도: 시간초과 ㅠㅅㅠ

_ = input()
target = list(input().split())
_ = input()
for i in input().split():
  if i in target:
    print("1")
  else:
    print("0")

Python 시간초과 해결하기

기본적으로 Python은 다른 언어에 비해서 느린 편이다. (물론 상대적으로 말이다!) JAVA나 C는 컴파일러가 따로 있어서 컴파일 한 파일만 후루룩 실행시키면 되지만, Python은 컴파일 없이 line-by-line해석하기 때문에 속도 차이가 발생한다. 그래서 백준에서 문제를 해결하다보면 종종 시간초과 문제에 봉착하게 된다. 이를 해결하기 위한 방법은 다음과 같다.

  1. 입력을 sys 모듈의 sys.stdin.readline() 함수를 사용하자.
    • 단 띄어쓰기(\n)도 함께 받아오는 것에 주의!
  2. 최대한 반복문을 줄이자.
  3. 재귀함수의 경우 메모이제이션 기법을 활용하자! 그럼 이제 반영해봅시다아아아

두 번째 시도: 여전히 시간초과…

import sys

_ = sys.stdin.readline()
target = list(sys.stdin.readline().split())
_ = sys.stdin.readline()
for i in sys.stdin.readline().split():
  if i in target:
    print("1")
  else:
    print("0")

또 시간초과에 빠졌다. 아무래도 input을 총 4번 받아보니 문제가 발생하는듯. 이걸 한번에 받고 나눌 수 있을까?

세 번째 시도: input을 한번에 받아두고 처리하자

import sys

nums = [0] * 4
for i in range(4):
  nums[i] = sys.stdin.readline().split()

for i in nums[3]:
  print('1') if i in nums[1] else print('0')

여전히 시간초과

네 번째 시도: 정렬하고 비교하자

import sys

_ = sys.stdin.readline()
A = set(map(int, sys.stdin.readline().split()))
_ = sys.stdin.readline()
B = list(map(int, sys.stdin.readline().split()))

for i in B:
  print('1') if i in A else print('0')

python 내장 set()을 이용하여 탐색 시간을 최소화하자. 그리고 for 문을 돌려서 그 안에서 input을 받는 것보다 그냥 일일히 input을 받는게 더 속도가 빠르다. 그리고 map()을 이용해서 문자(‘1’)를 숫자(1)로 바꿔주면 탐색에 더 빠르다.

구글링해보니 B 요소가 A에 속하는지 확인하기 위해 in 을 사용하는 대신에 이분탐색 알고리즘을 적용하는 해답도 보았다. target을 반으로 쪼개서 앞에 속하는지 뒤에 속하는지 비교를 반복해서 최종적으로 위치를 찾아내는 방법인데, in 사용하는게 더 빠르지만 알아둘 필요가 있다.