[백준] 1394 - 암호(Java)

문제 파악

https://www.acmicpc.net/problem/1394

어려운 점

• 암호의 길이가 최대 1,000,000로 길기 때문에 제곱 연산이 많이 이루어질 것이고, 자료형의 범위를 넘기도 한다.
• 첫 번째 라인에 주어진 문자열이 알파벳이 아닐 수 있음을 염두에 두자.

풀이

abc (암호로 사용할 수 있는 문자)
ccc (암호)

위를 예를 들어 계산해 보도록 하자

암호 입력은
a - b - c - aa - ab - ac - ba - bb - bc - ca - cb - cc - aaa - aab - (생략) - cca - ccb - ccc
순으로 이루어진다.

이를 조금 더 구분해 나누어 보자면 자릿수가 1개인 시도, 2개인 시도, 3개인 시도
a - b - c - aa - ab - ac - ba - bb - bc - ca - cb - cc - aaa - aab - (생략) - cca - ccb - ccc
로 나눌 수 있겠다.

그렇다면 앞선 한 자리 암호, 두 자리 암호 시도 횟수를 더해주고
세 자리 암호 시도 중 ccc에 해당하는 암호의 입력 순서를 더해주면 정답이 될 것이다.

📝 다시 정리해보며 수식을 세워 보자

편의를 위해
후보 문자열의 자리수 (예시에서는 abc의 길이인 3) = N
암호 문자열의 자릿수(예시에서는 ccc의 길이인 3) = K
라고 선언하여 사용한다.

1. 암호 자릿수 이전에 해당하는 연산 회수 계산

N ^ 1 + N ^ 2 + ... + N ^ (K-1)

2. 주어진 암호 자릿수의 시도 횟수 구하기

N ^ (K-1) * (후보 문자열 중 첫 번째 자리의 위치) + N ^ (K-2) * (후보 문자열 중 두 번째 자리의 위치) 
+ ... + N ^ 0 * (후보 문자열 중 마지막 자리의 위치)

조금 헷갈릴 수 있으니 위의 예시 (abc - ccc)를 대입해 보자
3 ^ 2 * 2 (abc 중 2번째에 위치) + 3 ^ 1 * 2 (마찬가지로 abc 중 2번째에 위치) + 3 ^ 0 * 2 (동일)

위의 1, 2 과정을 수행한 다음 1을 더해주면 정답이 될 것이다.

3. 제곱 연산 구현하기

그러나 제곱 연산이 많아지고, 정답을 구하기 위해서는 900528로 나눠주는 과정이 필요하다.

이 과정에서 제곱 연산과 모듈러 연산을 수행하는 함수를 따로 구현했으나, 타임아웃이 발생했다. 허허🥲
다양한 풀이 방법이 있겠지만 연산 회수를 줄이기 위해서 Map을 활용했다.

1,2 수식을 보면 후보 문자열의 자릿수(N)에 대한 제곱 연산이 대부분이므로,
지수를 키로 가지고, 엔트리(Key, Value)로 (0,1), (1,N)를 가지는 HashMap을 활용하여 연산을 수행하는 함수를 구현하였다.
이는 코드 내 customPow(int)로 구현되어 있다.

코드는 아래와 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static final int DIV = 900528;
    public static int cLen;
    public static Map<Integer, Long> powMap;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        powMap = new HashMap<>();
        String givenPasswordChar = br.readLine();
        String password = br.readLine();
        int n = password.length();
        cLen = givenPasswordChar.length();
        powMap.put(0, 1L);
        powMap.put(1, (long) cLen);
        long answer = 0;
        for (int i = 0; i < n - 1; i++) {
            answer = (answer + customPow(i + 1)) % DIV;
        }
        long attempt = 0;
        for (int i = 0; i < n; i++) {
            int k = givenPasswordChar.indexOf(password.charAt(i));
            attempt += (customPow(n - i - 1) * k) % DIV;
        }
        answer = (answer + attempt + 1) % DIV;
        System.out.println(answer);
    }

    private static long customPow(int pow) {
        if (powMap.get(pow) != null) {
            return powMap.get(pow);
        }
        long value = cLen * customPow(pow - 1) % DIV;
        powMap.put(pow, value);
        return value;
    }
}