문제
온라인 뱅킹에서 흔히 쓰이는 보안 기법 중에는, 비밀번호에 포함된 숫자를 랜덤하게 세 개 입력하도록 하는 것이 있습니다.
예를 들어 531278이라는 비밀번호에 대해서 2번째, 3번째, 5번째 숫자를 입력하도록 하는 식입니다. 이 때 올바른 입력은 317이 됩니다.
첨부한 텍스트 파일 keylog.txt에는 로그인에 성공한 어떤 사용자의 입력 기록이 50건 담겨져 있습니다. (비밀번호의 길이는 알 수 없습니다)
3개의 숫자는 항상 앞쪽부터 순서대로 요청된다고 할 때, 위의 접속 기록에서 알아낼 수 있는 가장 짧은 길이의 비밀번호는 무엇입니까?
접근
주어진 파일에는 3개의 숫자들로 구성된 정보들이 있다. 각 행의 3개의 숫자는 사용자가 입력한 숫자 3개이다. 이 정보로부터 우리는 각 숫자의 전후 관계를 알아낼 수 있다. 예시에서 317 이라는 입력이 있었는데, 최소한 1은 3보다는 뒤에, 그리고 7은 1과 3보다는 뒤에 있다는 사실을 알 수 있다.
이러한 정보가 여러 개 주어진다면, 각각의 숫자에 대해서 그 앞에 어떤 숫자가 올 것인지를 결정할 수 있다. 따라서 (숫자1개, {숫자 Set})의 형식으로 어떤 숫자와 그 숫자의 앞에 오는 숫자의 조합을 매 숫자마다 체크하고 이를 누적해 나갈 수 있다.
충분한 정보가 모였다고 가정할 때, 위 조합에서 두번째 요소인 숫자 집합의 원소가 많으면 많을수록, 첫번째 요소인 숫자는 전체 암호에서 뒤에 오는 숫자가 된다.
모든 정보를 처리한 후에, 후자의 개수를 기준으로 정렬하면 그 리스트의 맨 첫 원소는 두 번째 숫자에 관한 정보가 될 것이다. 그리고 맨 처음에 올 숫자는 첫 원소의 두 번째 요소, 즉 두 번째 숫자의 앞에오는 숫자가 될 것이다. 이를 코드로 풀어보자.
코드
from urllib.request import urlopen
url = 'http://euler.synap.co.kr/files/keylog.txt'
def p079():
data = urlopen(url).read().decode('utf8').splitlines()
cache = {}
for row in data:
# 각 행의 세 숫자
a, b, c = row.strip()
# 두 번째 숫자의 앞 숫자를 저장
cache.setdefault(b, set()).add(a)
# 세 번째 숫자의 앞 숫자들을 저장
cache.setdefault(c, set()).add(b)
cache.setdefault(c, set()).add(a)
# 선행숫자가 적은 순으로 정렬
xs = sorted(cache.items(), key=lambda x: len(x[1]))
f1 = xs[0][1].pop()
print(f1 + ''.join(x[0] for x in xs))