[백준 17219번] 비밀번호 찾기

문제 출처

문제 유형

• 자료 구조
• 해시를 사용한 집합과 맵

풀이

해당 문제는 solved.ac 사이트 기준 실버 4 문제입니다.

N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백을 기준으로 주어지고, 주어진 정보를 토대로 원하는 값을 찾아내는 문제입니다.

• 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)

• N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.

간단하게 생각하면 list로 저장할 수도 있겠지만, 문제의 조건에서 사이트 주소와 찾으려는 사이트가 최대 100,000개 이기때문에 시간복잡도가 오래걸립니다. 따라서 dictionary를 사용해 key와 value로 저장합니다. dictionary의 Insert Item과 Search Item은 전부 O(1)이기 때문에 간단하게 해결가능합니다.

또한, 100,000개가 한 줄씩 입력될수도 있기 때문에 sys.stdin.readline을 이용해 입력을 빠르게 받아옵니다.

풀이 코드

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
password = dict()

for _ in range(m):
    key, value = input().rstrip().split()

    # 사이트 key, value 저장
    password[key] = value

for _ in range(n):
    key = input().rstrip()
    
    # 패스워드 가져오기
    print(password[key])

sys.stdin.readline을 사용하면 저장되는 "\n" 값을 .rstrip()을 이용해 제거해줍니다.