[BAEKJOON] 2149 암호 해독 JAVA

몇 주 전부터 자체적으로 코딩테스트 스터디를 시작했다.

내가 푼 문제들을 작성해보면 좋을 것 같아서, 이번 주 과제 중 하나인 백준 암호 해독 문제를 가져왔다.

문제에서는 평서문을 암호문으로 만들 수 있는 조건을 알려준다.
입력 값으로 암호 해독 키와 암호문을 주면, 이걸 평서문으로 바꿔서 출력하면 되는 문제다.

이 문제를 풀기 위해 역으로 암호문을 평서문으로 만들기 위한 과정을 생각했다.

1. 암호 해독 키를 알파벳 순으로 정렬한다.
2. 암호문의 길이를 암호 해독 키의 길이로 나눈 길이만큼의 부분 문자열을, 1열부터 마지막 열까지 차례대로 넣어준다.
   • 암호문의 길이는 언제나 암호 해독 키의 배수라는 조건이 존재
3. 정렬된 암호 해독 키를 원래의 형태로 만든다.
   • 이때, 중복된 문자가 존재하면 먼저 들어온 순서대로 생성
   • 부분 문자열을 담은 열(Column)의 순서도 알파벳 위치대로 변경
4. 완성된 행렬 테이블을 1행부터 마지막 행까지 순서대로 읽어준다.

크게 말하자면 위의 네 단계로 볼 수 있다.

맨 처음에 생각했던 방법은, 이차원 배열을 사용하는 방법이었다.

그러나 원래 코딩 테스트를 파이썬으로 공부하다가 언어를 자바로 바꾼 거라 자바를 완전히 활용하지 못하고, 이차원 배열을 활용한 로직이 잘 생각나지 않아서 해시맵을 활용하는 코드로 변경했다.

총 두 개의 해시맵을 사용했는데, 하나는 암호 해독 키의 문자와 문자가 들어온 순서를 기억하기 위한 <Integer - Character> 쌍의 해시맵이다.
즉, 암호 해독 키의 들어온 순서와 문자를 기억한다.

다른 해시맵은 문자가 들어온 순서와 부분 문자열을 저장하는 <Integer - String> 쌍의 해시맵이다.
두 번째 해시맵을 통해 정답을 출력한다.

원래는 부분 문자열을 저장할 때 <Character - String> 쌍의 해시맵을 하나 추가해 사용했었는데, Character를 사용하니 들어온 순서를 기억 못 하는 걸 생각 못 하고 제출했다가 틀렸었다.

코드에 사용한 알고리즘은 아래와 같다.

1. <Integer - Character> 해시맵에 들어온 순서와 글자 저장
2. 암호 해독 키의 글자를 알파벳 순으로 해시맵 정렬
   • Value 값으로 해시맵 정렬
3. List를 생성해 해시맵의 KeySet 저장
   • 그냥 해시맵을 사용하면 0부터 차례대로 저장되기 때문에, LinkedHashMap을 사용해 Value 값으로 정렬되어 뒤죽박죽인 Key의 순서 그대로 저장
4. <Integer - String> 해시맵에 해독 키의 문자가 들어왔던 순서와 부분 암호문 저장
   • 들어온 순서는 정렬되어 있지 않음
   • 부분 암호문의 길이 = 암호문의 길이 / 암호 해독 키의 길이
   • 암호문의 첫 번째 글자부터 순서대로 저장
5. <Integer - String> 해시맵의 Key 값들을 들어온 순서대로 정렬
6. 각 Value 값의 첫 번째 글자를 모두 출력 후 두 번째 글자, 세 번째 글자, ..., 마지막 글자 순서대로 출력
   • 하나의 Value 값을 한 번에 모두 출력하는 게 아님
   • 모든 Value의 첫 글자를 순서대로 출력 후, 그 다음엔 모든 Value의 두 번째 글자를 순서대로 출력하여 마지막 글자까지 출력하는 과정
   • Value 값이 'Spring', 'Python'이라면 출력은 SPpyrtihnogn

코드에 대 한 설명은 모두 끝났으니, 어디 보여주긴 부끄러운 코드지만 코드를 띄우고 마무리하겠다.

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

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 pw = br.readLine();
        String sentence = br.readLine();

        int len = sentence.length() / pw.length();

        HashMap<Integer, Character> sequence = new HashMap<>();

        for (int i = 0; i < pw.length(); i++) {
            sequence.put(i, pw.charAt(i));
        }

        List<Map.Entry<Integer, Character>> list = new ArrayList<>(sequence.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<Integer, Character>>() {
            @Override
            public int compare(Map.Entry<Integer, Character> o1, Map.Entry<Integer, Character> o2) {
                return Character.compare(o1.getValue(), o2.getValue());
            }
        });

        LinkedHashMap<Integer, Character> sortedSequence = new LinkedHashMap<>();
        for (Map.Entry<Integer, Character> entry : list) {
            sortedSequence.put(entry.getKey(), entry.getValue());
        }

        List<Integer> keySets = new ArrayList<>(sortedSequence.keySet());

        HashMap<Integer, String> amo = new HashMap<>();



        int idx = 0;
        for(int i = 0; i < pw.length(); i++){
            int key = keySets.get(i);
            String subString = sentence.substring(idx * len, len * (idx + 1));

            amo.put(key, subString);
            idx++;
        }

        Collections.sort(keySets);


        int maxLength = amo.values().stream().mapToInt(String::length).max().orElse(0);

        for (int i = 0; i < maxLength; i++) {
            for (Integer key : amo.keySet()) {
                String value = amo.get(key);
                if (i < value.length()) {
                    bw.write(value.charAt(i));
                }
            }
        }

        br.close();
        bw.close();

    }
}