[백준] 1394 암호 - Java

 

 

 

암호에 쓰이는 문자들의 후보의 길이와 암호의 길이를 잘 살펴보자.

 

후보의 길이에 따라 시도하는 횟수가 점점 증가한다.

 

abcd가 후보라고 생각해보자.

 

길이가 1인 암호 : a b c d (4)

길이가 2인 암호 : aa ab ac ad / ba bb bc bd / ca cb cc cd / da db dc dd (4 * 4)

...

이런 식으로 후보문자열의 길이만큼 계속 곱해지는 형태를 보인다.

 

그렇다면, 주어진 암호의 길이를 통해 답을 어느정도 유추할 수 있을 것 같다.

 

그런데, 암호의 처음부터 계산해서 세기 시작하면 해당 자릿수 전까지의 시도 횟수는 쉽게 구할 수 있지만, 그 다음 처리가 힘들어진다. 

 

암호의 뒤에서부터 역순으로 시도 횟수를 구해보자.

 

이를 위해 문자열 후보가 입력되는 순서를 알아야한다.

문자열 후보를 입력받고, 배열을 통해 입력된 순서를 기록하자.

 

그 후 암호의 뒷부분부터 계산을 시작한다.

 

이 때 암호가 커지는 경우를 방지하기 위해 900528을 계속 나눠주자.

 

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String code = br.readLine();

		int sequence[] = new int[400];

		for(int i=1; i<code.length() + 1; i++){
			sequence[code.charAt(i - 1)] = i;
		}

		String password = br.readLine();

		int control = 1;
		int ans = 0; 	
		int cnt = code.length();

		for(int i = password.length() - 1; i>=0; i--){
			ans = (ans + control * sequence[password.charAt(i)]) % 900528;
			control = control * cnt % 900528;
		}

		System.out.println(ans);
		
		

	}
}