[SWEA 1242 : JAVA] 암호코드 스캔

문제

---

SWEA의 문제를 무단으로 복제하는 것은 금지입니다. 따라서, 링크를 달아두겠습니다.

----> SWEA_1242_암호코드 스캔

 

 

 

풀이

---

문제의 몇 가지 포인트는 다음과 같습니다.

1. 암호코드는 8개의 숫자다.
2. 입력이 16진수로 들어온다. (16진수 --> 2진수 변환필요)
3. 각 수(0~9)들은 0 1 0 1 순의 비율로 결정된다. ex) 5는 1:2:3:1 비율의 0 1 0 1 값이다. 0110001
4. 위 3번의 비율이 1배수가 아닐 수도 있다. ex) 위 5의 비율을 2배수로 표현하면 00111100000011 이다.
5. 암호코드가 여러 개 주어진다. (한 행에 여러 개의 암호코드가 있을 수 있다.)

 

해당 문제의 구현에서 어려운 부분은 4, 5번이라고 생각하기에 해당 부분만 설명하겠습니다.

먼저, 각 수(0~9)들은 0 1 0 1 순으로 나오기 때문에 행을 탐색할 때 뒤에서부터 탐색해야합니다. 앞에서부터 탐색하게되면 맨 앞에 나오는 0이 공백을 의미하는건지 암호코드의 일부를 의미하는지 알 수 없기 때문입니다. 뒤에서부터 탐색하다가 가장 먼저 1을 만나게되면 이는 암호코드의 마지막 부분이라는걸 확신할 수 있기 때문에 해당 부분부터 판별해나갑니다. 여기서 첫 번째 난관이 시작됩니다.

 

1을 시작지점으로 잡는건 알겠는데, 마지막지점은 어디까지일까요?

암호코드가 23456789(8개 숫자)에 대해 다음과 같이 입력이 들어왔다고 생각해보겠습니다.

괄호 안의 대응되는 숫자와 띄어쓰기는 보기 쉬우라고 적어논 것입니다. 실제 입력에선 이 둘이 없다고 생각해주세요.

000000 0010011(2) 0111101(3) 0100011(4) 0110001(5) 0101111(6) 0111011(7) 0110111(8) 0001011(9) 00000

--> 0000000010011011110101000110110001010111101110110110111000101100000

 

암호코드 8개의 숫자 중 뒤에서 7개(3456789)는 0과 1이 바뀌는 지점을 찾아 갯수를 구해줄 수 있습니다.

예를들어, 처음 1을 만난 지점에서 1이 2개, 0이 1개, 1이 1개, 0이 3개 순으로 나왔으니 3:1:1:2 비율을 가지는 것을 알 수 있고, 이 비율로 어떤 수를 의미하는지 찾아낼 수 있습니다. 그렇게 계속해 나가다가 마지막 수를 만나면 어떻게 될까요? (암호코드의 가장 첫 숫자 2)

 

1이 2개, 0이 2개, 1이 1개, ... 0은 몇 개지..?  탐색 기준으로 마지막 수는 첫 인덱스까지 0이란 값을 가집니다.

어떻게 해결할 수 있을까요?

 

문제를 잘 보면 0 1 0 1 의 4개 비율을 모두 보지 않고, 마지막 3개의 비율만 봐도 알 수 있다는 걸 알 수 있습니다.

ex) 9는 3:1:1:2를 가지는데, 3을 제외하고 뒤에서 3개 1:1:2만 보더라도 9라는걸 알 수 있습니다. (겹치지 않기 때문에)

 

 

 

코드

---

첫 번째 구현은 입력으로 들어오는 2차원 배열을 모두 저장한 후 판별을 하도록 구현했습니다.

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

public class Solution {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int T, N, M;
    static int[][] board;
    static StringBuilder sb = new StringBuilder();

    static int[][] hcode = {
            {0, 0, 0, 0}, // 0
            {0, 0, 0, 1}, // 1
            {0, 0, 1, 0}, // 2
            {0, 0, 1, 1}, // 3
            {0, 1, 0, 0}, // 4
            {0, 1, 0, 1}, // 5
            {0, 1, 1, 0}, // 6
            {0, 1, 1, 1}, // 7
            {1, 0, 0, 0}, // 8
            {1, 0, 0, 1}, // 9
            {1, 0, 1, 0}, // A
            {1, 0, 1, 1}, // B
            {1, 1, 0, 0}, // C
            {1, 1, 0, 1}, // D
            {1, 1, 1, 0}, // E
            {1, 1, 1, 1}, // F
    };

    static int[][][] rate = new int[5][5][5];

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            board = new int[N][M * 4];

            for (int i = 0; i < N; i++) {
                String str = br.readLine();
                for (int j = 0; j < M; j++) {
                    char c = str.charAt(j);
                    int num = Character.digit(c, 16);
                    for (int k = 0; k < 4; k++) {
                        board[i][j * 4 + k] = hcode[num][k];
                    }
                }
            }

            init();

            int ans = 0, codeLen = 7;
            int[] codes = new int[8]; // 암호코드 8개의 숫자를 담을 공간.
            for (int i = 1; i < N; i++) {
                for (int j = M * 4 - 1; j >= 0; j--) {
                    if (board[i][j] == 1 && board[i - 1][j] == 0) { // 암호코드 우측 최상단
                        int x, y, z;
                        x = y = z = 0;

                        while (board[i][j] == 1) { z++; j--; }
                        while (board[i][j] == 0) { y++; j--; }
                        while (board[i][j] == 1) { x++; j--; }
                        if (codeLen != 0) { while (board[i][j] == 0) { j--; } }
                        j++;

                        int min = Math.min(Math.min(x, y), z); // 1 비율의 값을 구한다.

                        x /= min; y /= min; z /= min; // 암호코드의 비율을 1배수로 만든다.
                        codes[codeLen--] = rate[x][y][z];

                        if (codeLen == -1) {
                            int checkVal = (codes[0] + codes[2] + codes[4] + codes[6]) * 3 + codes[1] + codes[3] + codes[5] + codes[7];
                            if (checkVal % 10 == 0) { for (int item : codes) ans += item; }
                            codeLen = 7;
                        }
                    }
                }
            }

            sb.append("#").append(tc).append(" ").append(ans).append("\n");
        }

        System.out.println(sb);
    }

    private static void init() {
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k < 5; k++)
                    rate[i][j][k] = -1;

        rate[2][1][1] = 0;
        rate[2][2][1] = 1;
        rate[1][2][2] = 2;
        rate[4][1][1] = 3;
        rate[1][3][2] = 4;
        rate[2][3][1] = 5;
        rate[1][1][4] = 6;
        rate[3][1][2] = 7;
        rate[2][1][3] = 8;
        rate[1][1][2] = 9;
    }
}

 

두 번째 구현은 입력으로 들어온 2차원 배열을 별도로 저장하지 않고, 행 단위로 바로바로 처리하도록 구현했습니다.

(첫 번째 방법보다 메모리 절약과 시간이 조금 더 빠릅니다.)

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

public class Solution {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int T, N, M;
    static StringBuilder sb = new StringBuilder();

    static int[][] hcode = {
            {0, 0, 0, 0}, // 0
            {0, 0, 0, 1}, // 1
            {0, 0, 1, 0}, // 2
            {0, 0, 1, 1}, // 3
            {0, 1, 0, 0}, // 4
            {0, 1, 0, 1}, // 5
            {0, 1, 1, 0}, // 6
            {0, 1, 1, 1}, // 7
            {1, 0, 0, 0}, // 8
            {1, 0, 0, 1}, // 9
            {1, 0, 1, 0}, // A
            {1, 0, 1, 1}, // B
            {1, 1, 0, 0}, // C
            {1, 1, 0, 1}, // D
            {1, 1, 1, 0}, // E
            {1, 1, 1, 1}, // F
    };

    static int[][][] rate = new int[5][5][5];

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            init();

            int ans = 0, codeLen = 7;
            int[] codes = new int[8]; // 암호코드 8개의 숫자를 담을 공간.
            String prev = br.readLine();
            int[] binaryRow = new int[M * 4];
            int[] prevBinaryRow = new int[M * 4];

            for (int i = 1; i < N; i++) {
                String row = br.readLine();
                if (prev.equals(row)) continue;
                prev = row;

                // 16진수로 되어있는 행 --> 2진수 행으로 변환하기.
                for (int j = 0; j < M; j++) {
                    int num = Character.digit(row.charAt(j), 16);
                    for (int k = 0; k < 4; k++) { binaryRow[j * 4 + k] = hcode[num][k]; }
                }

                for (int j = M * 4 - 1; j >= 0; j--) {
                    if (binaryRow[j] == 1 && prevBinaryRow[j] == 0) { // 암호코드 우측 최상단
                        int x, y, z;
                        x = y = z = 0;

                        while (binaryRow[j] == 1) { z++; j--; }
                        while (binaryRow[j] == 0) { y++; j--; }
                        while (binaryRow[j] == 1) { x++; j--; }
                        if (codeLen != 0) { while (binaryRow[j] == 0) { j--; } }
                        j++;

                        int min = Math.min(Math.min(x, y), z); // 1 비율의 값을 구한다.

                        x /= min; y /= min; z /= min; // 암호코드의 비율을 1배수로 만든다.
                        codes[codeLen--] = rate[x][y][z];

                        if (codeLen == -1) {
                            int checkVal = (codes[0] + codes[2] + codes[4] + codes[6]) * 3 + codes[1] + codes[3] + codes[5] + codes[7];
                            if (checkVal % 10 == 0) { for (int item : codes) ans += item; }
                            codeLen = 7;
                        }
                    }
                }
                prevBinaryRow = binaryRow.clone();
            }

            sb.append("#").append(tc).append(" ").append(ans).append("\n");
        }

        System.out.println(sb);
    }

    private static void init() {
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k < 5; k++)
                    rate[i][j][k] = -1;

        rate[2][1][1] = 0;
        rate[2][2][1] = 1;
        rate[1][2][2] = 2;
        rate[4][1][1] = 3;
        rate[1][3][2] = 4;
        rate[2][3][1] = 5;
        rate[1][1][4] = 6;
        rate[3][1][2] = 7;
        rate[2][1][3] = 8;
        rate[1][1][2] = 9;
    }
}