백준 1394번: 암호

임의의 순서대로 암호에 사용할 문자들이 주어질 때, 암호를 해독하는데 필요한 시도 횟수를 900528로 나눈 나머지를 출력하는 문제이다. 시도 횟수 = (길이 1~L-1인 문자열 수) + (길이 L인 문자열 중 순서) 로 생각하여 풀이하였다.

 

먼저 문자들의 순서 저장을 위해 Map에 저장하였다.

Map<Character, Integer> indexMap = new LinkedHashMap<>();
for (int i = 0; i < N; i++) {
    indexMap.put(chars.charAt(i), i);
}

 

 

길이 L의 암호를 만들기 위해서 이전에 1~L-1 의 암호를 만들어야 한다. 이를 만드는 경우의 수는 각각 (암호에 사용할 문자의  수) ^ 길이 즉, N + N^2 + ... + N^(L-1) 이다. 

long prefixCount = 0;
long power = 1;
for (int k = 1; k <= L - 1; k++) {
    power = (power * N) % MOD;
    prefixCount = (prefixCount + power) % MOD;
}

 

 

이후, 길이 L인 문자열 중 암호의 순서를 구한다. 각 문자의 인덱스를 N개 중 1개이므로 N진법 수로 해석하여 적용한다. 

long position = 0;
for (int i = 0; i < L; i++) {
    int digit = indexMap.get(password.charAt(i));
    position = (position * N + digit) % MOD;
}
position = (position + 1) % MOD;

 

 

결과 코드는 다음과 같다.

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

public class 암호1394 {
    
    static final long MOD = 900528;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String chars = br.readLine();
        String password = br.readLine();
        
        int N = chars.length();
        int L = password.length();
        
        Map<Character, Integer> indexMap = new LinkedHashMap<>();
        for (int i = 0; i < N; i++) {
            indexMap.put(chars.charAt(i), i);
        }
        
        long prefixCount = 0;
        long power = 1;
        for (int k = 1; k <= L - 1; k++) {
            power = (power * N) % MOD;
            prefixCount = (prefixCount + power) % MOD;
        }
        
        long position = 0;
        for (int i = 0; i < L; i++) {
            int digit = indexMap.get(password.charAt(i));
            position = (position * N + digit) % MOD;
        }
        position = (position + 1) % MOD;
        
        System.out.print((prefixCount + position) % MOD);
    }
}