[99클럽 코테 스터디 TIL 1일차 / 백준 2776] 암기왕 (Python)

오늘부터 항해99 코테 스터디를 통해서 평일동안 매일 주어지는 문제를 푼다 !

스터디의 첫문제가 바로 백준의 암기왕 문제였다.

 

문제를 처음 확인했을때 난이도가 실버4여서 당황했다... 물론 실버 + 골드5가 미들러 난이도이긴 하지만 보통 실버1,2, 골드5 문제를 풀기때문에 실버4는 너무 쉽기 때문이다...

 

일단 문제를 읽었을 때 단순히 입력값을 받고 note2의 요소가 note1에 있는지 확인하는 문제라고 판단하고 코드를 작성하였다.

 

첫 코드

t = int(input())


for _ in range(t):
    n1 = int(input())
    note1 = list(map(int, input().split()))
    n2 = int(input())
    note2 = list(map(int, input().split()))
    
    for n in note2:
        if n in note1:
            print(1)
        else:
            print(0)

결과 값은 제대로 나오는데 시간초과가 발생하였다.

 

솔직히 시간초과의 이유를 모르겠어서 질문 게시판을 참고하게 되었다.

질문 게시판을 확인하니 

if n in note1:

이 부분에서 시간초과가 발생한다는 것을 알게되었다.

list에 in을 사용해서 조사할 경우 dict와 set에 비해 시간이 훨씬 오래걸리기 때문이다.

그래서 note1만 집합으로 바꾸어 주었다.

 

최종 코드

t = int(input())


for _ in range(t):
    n1 = int(input())
    note1 = set(map(int, input().split()))
    n2 = int(input())
    note2 = list(map(int, input().split()))

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

 

이렇게 note1을 집합으로 만들어 주니 맞았습니다!가 떴다.

 

시간초과가 발생하는 원인이 너무 다양해서 해결하기가 너무 어려운 것 같다..

 

그래도 이렇게 경험을 쌓다보면 나중엔 더욱 쉽게 원인이 무엇인지 찾을 수 있을 것이라고 기대한다 !

 

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