[백준/파이썬] 1920 수 찾기 : 이진검색트리 말고 세트(집합)으로 풀기, 시간초과 나는 이유

백준 1920 수 찾기를 풀었습니다.

1년 전에 시간 초과가 계속 떠서 포기했던 문제인데,

이번에 다시 도전해본 문제입니다.

 

군대 문제로 자료구조 공부를 아직 못했기에 이진검색트리 같은 건 잘 모르지만,

첫 입력하는 수들을 세트(집합)로만 바꿔도 시간초과 문제가 해결될 수 있었습니다.

 

아래 코드를 확인해주세요

 

SMALL

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

728x90

 

import sys

n = int(sys.stdin.readline())
numSet1 = set(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
numSet2 = list(map(int, sys.stdin.readline().split()))

for i in range(m):
    compare = numSet2[i]
    result = 0
    if compare in numSet1:
        result = 1
        
    print(result)

반응형

 

풀이 아이디어

1. 수 입력 : input()이 아닌 sys.stdin.readline()을 이용한다는 건 다들 아실 겁니다. 반면 제가 헷갈렸던 건, 숫자 하나를 입력할 때 마지막 공백을 rstrip()으로 지우느냐였는데, int로 묶어주기 때문에 마지막 공백은 자연스레 사라진다고 합니다. 헷갈리시는 분들은 참고 바랍니다.

2. 첫번째 입력받는 수들과 두번째 입력받는 수들을 저장하는 자료구조를 각각 Set과 List로 했습니다. 두번째 수들을 순서대로 비교하여 첫번째 수들에 있는 수인지를 알아보는 코드가 되어야 하는데, 첫번째 수들 안에 있는지만 확인하면 되니 첫번째 수들의 순서는 필요가 없습니다.

3. 굳이 compare을 쓰지 않아도 될 것으로 보입니다.

4. bool형을 사용할까 했지만, 1과 0을 출력해야 하기에, 숫자가 없는 상태를 0, 숫자가 있는 상태를 1이라고 했습니다. 없는 상태를 기본값으로 초기화했다가, 있다면 1을 다시 할당하는 방식으로 코드를 짰습니다.

 

*주의사항*

1. 시간 초과 문제가 중요하므로 input이 아닌 sys.stdin.readline() 꼭 쓰기

2. Set을 쓰기

3. 이진 탐색을 이용하기

4. 무의미한 반복 루프가 돌아가지 않도록 주의하기 : 예를 들어, if A in B 형태가 아닌 if A[i] == B[k] 같은 형태로 했을 경우, 안에 들어있음을 확인한 후에도 비교를 하고 있는지 확인