[백준][진법] 1394. 암호

1394. 암호

1394번: 암호

 

• 다른 사람 풀이
  • n 진법인 이유
    • 10 진법: 0~9까지 10가지 수로 10^n, 10^n-1.... 10^2, 10^1, 10^0 위치로 값을 구하는 것
    • ex) abcdef -> 6진법 
      • bd = 2*6^1 + 4*6^0 = 12+4= 16
  • 이분탐색 안하면 시간초과남!!

from collections import defaultdict

# x의 y승을 이분탐색으로 log시간으로 단축해서 계산
def power(x, y, p):
    result = 1
    x = x % p
    while y > 0:
        if y % 2 == 1:
            result = (result * x) % p #아랫쪽에서 y를 반으로 나누면서 계산해둔 x^2를 여기서 곱함
        y = y // 2
        x = (x * x) % p
    return result


code = input()
hash_table = defaultdict(int)
for i in range(len(code)):
    hash_table[code[i]] = i+1

string = input()
answer = 0
l = len(string)
code_len = len(code)
MOD = 900528

for i in range(l):
    exp = (l-1-i)
    answer = (answer + (hash_table[string[i]] *
              power(code_len, exp, MOD)) % MOD) % MOD

print(answer)