[코드트리] 치환 암호 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/substitution-cipher?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

암호 방식에는 여러 가지가 있습니다. 그중 우리는 치환 암호를 복호화해보려고 합니다.

치환 암호란, a ~ z 각각을 다른 문자로 변경하는 작업입니다. 예를 들어 a를 c, b를 a, c를 b로 치환한다면 bca라는 문자열은 abc가 될 것입니다.

치환 규칙과 암호화된 문자열이 주어졌을 때 원문을 구해내는 프로그램을 작성해 보세요.

예로 치환 규칙이 cab, 암호화된 문자열이 abc로 주어졌다면, 답은 원문에 해당하는 bca가 됩니다.

 

입력 예시

j ibwf b tbnqmf
bcdefghijklmnopqrstuvwxyza

 

출력 예시

i have a sample

 

 

코드

첫 번째 줄에 암호화된 문자열이 주어지고, 두 번째 줄에는 치환 규칙에 해당하는 문자열이 주어진다.

• 1 <= 암호화된 문자열의 길이 <= 100
• 치환 규칙에 해당하는 문자열의 길이 = 26 (a부터 z까지 해당하는 대체 문자)

 

반복문 사용

import java.io.*;

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

        String str = br.readLine();
        char[] hash = br.readLine().toCharArray();

        for (int i = 0; i < str.length(); i++) {
            char current = str.charAt(i);

            // 현재 문자가 공백(' ')이면 그대로 출력
            if (current == ' ') {
                bw.write(current);
                continue;
            }

            // hash 배열을 순회
            for (int j = 0; j < hash.length; j++) {
                // 현재 문자가 hash[j]와 같으면 'a' + j 출력
                if (current == hash[j]) {
                    bw.write('a' + j);
                    break;
                }
            }
        }

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

 

Map 사용

import java.io.*;
import java.util.HashMap;
import java.util.Map;

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

        String str = br.readLine();
        char[] hash = br.readLine().toCharArray();

        // 문자를 key, 인덱스 i를 value로 갖는 map 초기화
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < hash.length; i++) {
            map.put(hash[i], i);
        }

        for (int i = 0; i < str.length(); i++) {
            char current = str.charAt(i);

            // 현재 문자가 공백(' ')이면 그대로 출력
            if (current == ' ') {
                bw.write(current);
                continue;
            }

            // map의 current에 해당하는 값을 'a'에 더하여 출력
            bw.write('a' + map.get(current));
        }

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

• 반복문을 사용할 경우 O(n^2)의 시간복잡도를 가지는 반면에, map을 사용하는 경우 O(n)의 시간 복잡도를 가진다.