[Python][백준] 17219번 비밀번호 찾기 문제 풀이

이 문제는 자료구조와 해시를 사용한 집합과 맵이 핵심 개념이다.

 

이 문제를 풀때, 일반적인 리스트로 풀면 시간초과의 늪에 빠질 것이다.

 

이 때 사용해야 할것이 Python의 dictionary 자료구조이다. (c++, java의 map)

 

dictionary는

키(key)와 값(value)이 쌍을 이루는 자료구조로, 순서와 상관없이 키 값으로 한 번에 값을 불러올 수 있다.

dictionary는 해시로 이루어져있기 때문에, 값을 불러 올 때의 시간복잡도는 O(1)이다.

 

이를 코드로 구현하면 다음과 같다.

import sys


def P17129():
    n1, n2 = map(int, input().split())

    # 사이트의 주소와 비밀번호 입력
    sites = {}
    for _ in range(n1):
        s, p = input().split()
        sites[s] = p

    for _ in range(n2):
        print(sites[input().strip()])


if __name__ == '__main__':
    input = sys.stdin.readline
    P17129()

위 코드는 아래와 같이 더 간단하게 표현할 수 있다.

import sys

input = sys.stdin.readline
n1, n2 = map(int, input().split())
sites = dict(input().split() for _ in range(n1))
print(*list(sites[input().strip()] for _ in range(n2)), sep='\n')