[Gold V] 암호 - 1394

문제 링크

성능 요약

메모리: 113544 KB, 시간: 168 ms

분류

조합론, 자료 구조, 해시를 사용한 집합과 맵, 수학, 문자열

제출 일자

2024년 7월 23일 18:07:25

문제 설명

유진이는 현수의 암호를 알아내려고 한다. 유진이는 사전 조사를 통해 임현수의 컴퓨터에 어떤 문자들이 쓰이는지 알아내었고, 하나씩 대입해보려고 한다. 대입하는 순서는 유진이가 메모한 문자 집합의 순서대로이고, 한 글자부터 암호가 풀릴 때까지 모두 대입해본다.

예를 들어, 메모한 문자 집합이 bca라고 한다면, 유진이는 b, c, a, bb, bc, ba, cb, cc, ca, ab, ac, aa, bbb, bbc, ........ 순서로 암호가 풀릴 때까지 계속 대입해본다.

입력

첫 번째 줄에는 암호로 사용할 수 있는 문자가 공백 없이 주어지고, 두 번째 줄에는 컴퓨터의 암호가 주어진다. 암호에 사용할 수 있는 문자의 종류는 최대 100가지이고, 공백은 사용할 수 없다. 영문자는 대소문자를 구분한다. 암호의 길이는 최대 1,000,000자이다.

출력

첫 번째 줄에 주어진 암호를 몇 번의 시도로 풀 수 있는지 출력한다. 만약 수가 클 경우, 시도 횟수를 900528으로 나눈 나머지를 출력한다.

풀이

처음에 제곱 연산자를 썼다가 시간 초과가 났다.

제곱 연산자를 쓰는 대신 입력한 문자의 길이만큼 계속 곱해주며 modulo 연산자를 사용하는 게 point!

코드

import sys

input = sys.stdin.readline

can_be_password=input().strip()
input_len = len(can_be_password)
password=input().strip()
try_num=0
pass_len = len(password)

for i in password:
    index = can_be_password.index(i)
    try_num+=(index+1)
    if pass_len>1:
        try_num*=input_len
        try_num%=900528
    pass_len-=1

print(try_num%900528)