TIL 23-07-07 백준 알고리즘 - 암기왕

1.백준 알고리즘 - 암기왕

 문제점

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

2776번: 암기왕

 시도해 본 것들

최초 작성 코드 

from sys import stdin

for _ in range(int(stdin.readline())):
    N = int(stdin.readline())
    N_word = {i: True for i in list(map(int, stdin.readline().split()))}
    M = int(stdin.readline())
    M_word = list(map(int, stdin.readline().split()))
    for m in M_word:
        print(int(N_word.get(m, False)))

통과는 했지만, 1600ms라는 시간이 마음에 들지 않고, 코드도 간략하게 만들고 싶었다. 

 해결 방법

# 최종 개선 버전
# 입력이 1,000,000개까지 들어올 수 있으므로 빠른 입출력 사용
from sys import stdin

for _ in range(int(stdin.readline())):
    N = int(stdin.readline())
    # dictionary comprehension을 통한 dict 선언
    N_word = {i: "1" for i in list(map(int, stdin.readline().split()))}
    M = int(stdin.readline())
    M_word = list(map(int, stdin.readline().split()))
    # N_word.get(m, "0") n_word라는 dict에 m이라는 key가 존재하면 그 value를 가져오고,
    # 없을 경우 m을 key로 하는 "0"의 value를 생성
    # join을 사용하기 위한 형변환 과정을 최소화 하기 위해 int, boolean 대신 str로 value설정
    print("\n".join([N_word.get(m, "0") for m in M_word]))

 

필요 없을 것 같은 과정을 제거하며 속도가 크게 개선 됐다. 

 알게 된 점

dictionary를 활용할 때 comprehension과 get()함수를 익숙하게 사용이 가능해졌다. 

문제를 더 잘 이해하기 위해서 펜과 노트로, 최소 주석으로 문제에 대한 설명 작성해보기 

문제를 풀며 걸리는 시간을 측정하고 이에 대한 수준을 확인하고 문제의 난이도를 높이지 못하면 시간이 단축될 수 있도록 하기