14584번(암호 해독)

첫 시도

• 암호문의 길이는 100 이하, N은 20, N의 길이는 20이다.
• 문제를 해결하기 위해 해야하는 작업이 2가지가 있다
  1. 암호문의 모든 문자를 한칸 씩 옆으로 옮기기 -> 모든 경우를 확인해야 하기 때문에 26번 반복
  2. 사전에 등록된 단어가 해독된 문자열에 있는지 확인, 1개라도 있으면 해당 문자열이 잘 해독된 문자열
• 시간복잡도는 26 * (100 + (20 * 20)) -> 26 * 4 * 10^4

해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        String str = br.readLine(); // 암호문

        int N = Integer.parseInt(br.readLine());
        String[] words = new String[N]; // 사전에 있는 단어들
        String result = "";
        for(int i = 0; i < N; i++){
            words[i] = br.readLine();
        }
        for(int i = 1; i < 26 + 1; i++){ // 알파벳 갯수가 26개, 모든 경우의 수를 확인
            String pw = "";
            for(int j = 0; j < str.length(); j++){
                char alpa = (char) (str.charAt(j)+i); // char a = 'a';일때 a + 1 은 98, 즉 'b'다. 
                if(alpa > 122) alpa -= 26; // z를 벗어나면 a로 돌아가게 구현
                pw += alpa;
            }

            for(int j = 0; j < N; j++){
                if(pw.contains(words[j])){ // 해독된 암호에 사전의 문자가 있는지 확인
                    result = pw;
                    break;
                }
            }
        }
        System.out.println(result);
    }
}

참고

• 직접구현