[BOJ][Java] 백준 1394번: 암호

문제 설명

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

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

 

제한조건

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

 

문제 풀이

 

문제풀이공식

이 문제에서 보시면

bc = b*암호의 길이+c의 순서 = 1*3+2 = 5      //      bcb = bc*암호의 길이 * b의 순서 = 5*3+1 = 16 가 성립합니다.

 

즉 이 문제는 위의 규칙을 찾아낼 수 있다면 해결할 수 있는데 한가지 문제점이 있습니다. 바로 시간 제한인데요. 

문자의 위치가 어디에 있는지 찾아야 하기 때문에 for문을 통해 암호의 길이만큼 계속 탐색하게 된다면 시간초과가 날 것입니다. 이를 해결하기 위해 이분탐색을 활용하여 걸리는 시간을 줄였습니다.

풀이 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st = new StringTokenizer("");
    static StringBuilder sb = new StringBuilder("");

    static final int MOD = 900528;
    static Code[] codes;
    static String computerCode;

    static void input() throws IOException {
        String[] line = br.readLine().split("");
        codes = new Code[line.length];
        for(int i=0; i<line.length; i++) codes[i] = new Code(line[i], i+1);
        Arrays.sort(codes);
        computerCode = br.readLine();
    }

    static void process() {
        long ans = 0;
        for(int i=0; i<computerCode.length(); i++){
            ans = (ans * codes.length + findStr(computerCode.substring(i, i+1))) % MOD;
        }
        System.out.println(ans%MOD);
    }

    static int findStr(String str){
        int L = 0, R = codes.length-1, pos=R;
        while(L<=R){
            int mid = (L+R)/2;
            if(str.compareTo(codes[mid].str) < 0){
                R = R-1;
                pos = R;
            }else{
                L = L+1;
            }
        }
        return codes[pos].idx;
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }

    static class Code implements Comparable<Code>{
        String str;
        int idx;

        Code(String str, int idx){
            this.str = str; this.idx = idx;
        }

        @Override
        public int compareTo(Code c) {
            if(!this.str.equals(c.str)) return this.str.compareTo(c.str);
            return this.idx - c.idx;
        }

        @Override
        public boolean equals(Object object){
            Code code = (Code)object;
            if(this.str.equals(code.str)) return true;
            return false;
        }
    }
}

 

<출처>

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

1394번: 암호