BOJ_1394_암호 (Java)

[Gold V] 암호 - 1394

문제 링크

성능 요약

메모리: 28008 KB, 시간: 272 ms

분류

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

제출 일자

2025년 3월 4일 02:42:06

문제 설명

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

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

입력

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

출력

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

문제 풀이

암호의 길이가 M일때 1~(M-1)까지의 경우의수는 모두 더해줘야한다. 그걸 다 더해주고,

길이 M일땐 각 위치마다 특정 문자가 잇을건데 그 문자 전 개수 x (전체 문자 개수) ^ (남은 길이) 만큼씩 곱해줘야한다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static String N, M;
    static int N_len, M_len;
    static final int MOD = 900528;
    static long res = 0;
    static Map<Character, Integer> charPos = new HashMap<>();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1394_암호/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = br.readLine();
        M = br.readLine();
        N_len = N.length();
        M_len = M.length();

        /*
        M_len-1까지 모든 경우의수는 다 더해야함. 길이 0이면 0
        나머지 M_len의 경우의수 추가
         */

        long power = N_len;
        for (int i = 1; i < M_len; i++) {
            res = (res + power) % MOD;
            power = (power * N_len) % MOD;
        }

        for (int i = 0; i < N_len; i++) {
            charPos.put(N.charAt(i), i);
        }

        long[] weights = new long[M_len];
        weights[M_len - 1] = 1;

        for(int i = M_len - 2; i >= 0; i--) {
            weights[i] = (weights[i + 1] * N_len) % MOD;
        }

        for (int i = 0; i < M_len; i++) {
            char curr = M.charAt(i);
            int currPos = charPos.get(curr);

            res = (res + (currPos * weights[i]) % MOD) % MOD;

        }

        // 마지막에 암호 자체도 카운트
        res = (res + 1) % MOD;

        System.out.println(res);

        bw.flush();
        bw.close();
        br.close();
    }
}