📜문제 설명

문제 바로가기

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

📍입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

1
5
4 1 5 2 3
5
1 3 7 9 5

📍출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

1
1
0
0
1

---

📄문제 해결

📝내가 푼 코드

for _ in range(int(input())):
    N = int(input())
    # 순서가 중요하지 않으니 set으로 저장
    note1 = set(map(int, input().split(' ')))

    M = int(input())
    note2 = list(map(int, input().split(' ')))

    for n in note2:
        if n in note1: print(1)
        else: print(0)

문제는 나중에 주어지는 수첩2의 정수들이 먼저 주어진 수첩1에 포함된지 여부를 판단한다. 로직은 바로 떠올라 간단했지만, 문제는 시간 제한이 존재한다는 점이었다.

첫 번째로 코드를 작성했을 때는 note1 도 note2 와 마찬가지로 리스트로 저장하는 방식을 사용했으나, 시간 초과가 발생했다. 이때 시간을 줄이기 위해 note1의 자료형을 바꾸었다. note2는 저장된 값의 순서대로 결과를 출력해야하고, note1은 저장된 값의 순서가 중요하지는 않기 때문에 note1만 set으로 바꾸었다.

---

🤔느낀점

단순히 로직만 맞게 구현하는 것이 아니라, 다른 자료형을 선택함으로써 시간복잡도를 최적화하는 과정이 필요함을 느낄 수 있었다.