[SWEA] 1242번 암호코드 스캔 자바(java) 풀이

sw expert academy 1242 암호코드 스캔 자바(java) 풀이

• 난이도 : D5
• sw expert academy 1242 암호코드 스캔
  
  
  

문제 정리

1. 암호는 총 8개의 숫자로 이루어져있다.
2. 앞 7자리는 상품 고유의 번호를, 마지막 자리는 검증코드를 나타낸다.
3. 검증코드 계산은 다음과 같이 한다.
   • (홀수 자리의 합 * 3 ) + 짝수 자리의 합 + 검증 코드는 10의 배수가 되어야 한다.
4. 암호코드 숫자 하나의 길이는 최소7이며 7의 배수로 늘어날 수 있다. (각 숫자는 흰색과 파란색의 넓이 비로 표현된다)
   • 원래 9인 "0001011"의 비는 3:1:1:2이다. 2배로 늘어나게 되면 "00000011001111"이 된다. 비율은 같으므로 이도 9를 표현한다.
5. 암호코드에 포함된 숫자들의 합을 출력한다.
   
   
   

문제 풀이

처음에는 문제 이해부터 힘들었습니다...
배열에 하나의 암호코드가 아니라 여러개의 암호코드가 들어있을 수 있습니다.
그때 들어있는 모든 암호코드를 숫자로 변환하여 합을 구해야합니다.
같은 암호코드가 여러줄에 걸쳐서 쓰여있는데 이 경우 모든 줄의 암호코드를 숫자로 바꿔서 더하는 것이 아니라
같은 줄 중 하나의 암호코드만 숫자로 변환하여 더해주면 됩니다!!

암호문을 2진수로 변환해서 풀어야 합니다.

1. 숫자 암호들은 0으로 시작해서 '0101'의 패턴을 가지고 1로 끝납니다

   • 오른쪽에서 부터 탐색하여 1이 처음 나오고 그 위에 숫자가 0이라면 바코드의 우상단임을 알 수 있습니다. 이 경우만 암호코드의 값을 게산하면 같은 암호코드를 계산할 일이 없습니다.

2. 배수는 어떻게 판단할 것인가?

   • 2 4 6 2가 나왔다고 하자. 그러면 가장 작은 수의 배수가 됨을 알 수 있습니다. (모두 1을 포함함)
   • 가장 작은 수가 2이므로 2로 나누어줘서 1232가 됨을 알 수 있습니다.
   • 오른쪽의 3수가 모두 다르므로 오른쪽의 3개의 수만 봐도 됩니다.
   • code를 다음과 같이 판별 할 수 있습니다.

     0은 3:2:1:1이다. 이중 오른쪽 3개의 수는 2:1:1이다.
     이를 s[2][1][1] = 0로 표현합니다.
     1는 s[2][2][1] = 1로 표현합니다.
     나머지 수들도 마찬가지입니다.

     integer형으로 바꾸어서 bit shift 연산을 통해 번역하지 않고 하나씩 읽어가며 할 수 있습니다.

3. 이전 줄과 같은 줄은 입력받은 경우 스킵
   이는 구현하지 않아도 통과할 수 있습니다.
   입력을 보면 똑같은 줄이 많이 주어집니다. 이러한 경우 이전 줄과 같으면 탐색을 하지 않고 skip하게 되면 더 빠른 시간안에 답을 도출할 수 있습니다.
   skip 하는 부분을 추가함으로써 200ms 가까이 빠르게 답을 낼 수 있었습니다.

4. 암호코드에 포함된 숫자 계산
   암호코드는 오른쪽의 3개의 수만 보면 됩니다. 이를 x,y,z 변수를 이용하여 찾습니다.
   코드는 0/1/0/1이 번갈아서 나옵니다.
   뒤에서 부터 탐색하므로 뒤의 1의 개수를 z, 뒤의 0의 개수를 y에, 앞쪽의 1의 개수를 x에 담습니다.
   이렇게 1/0/1의 각각 개수를 찾고 최소 값을 찾아서 그 값으로 나누어 주게 되면 어떤 숫자를 나타내는지 num배열을 통해 알 수 있습니다.

swea 암호코드 스캔 자바 코드

코드를 아래에 첨부하며 주석도 달아두었으니 참고하시기 바랍니다.

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

class Solution {
    static char[][] map;
    static int width, height;
    static int[][][] num;
    static int ans;

    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
    };

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            String[] temp = br.readLine().split(" ");
            height = Integer.parseInt(temp[0]);
            width = Integer.parseInt(temp[1]);

            num = new int[4][3][4];
            map = new char[height][width*4];
            initCode();

            int codeLen = 7;
            int[] code = new int[8];
            ans = 0;

            // 암호
            String before = "";
            for(int i=0; i<height; i++){
                String input = br.readLine();

                // 첫 줄 or 이전 줄과 똑같을 경우 탐색 X
                if(input.equals(before) || i == 0) {
                    before = input;
                    continue;
                }

                // map 만들기
                String[] temp2 = input.split("");
                makeMap(before.split(""), i-1);
                makeMap(temp2, i);

                // 암호코드 탐색
                for(int j=width*4-1; j>0; j--){
                    // 바코드의 우상단인 경우
                    if(map[i][j] != '\0' && map[i-1][j] == '\0'){
                        int x,y,z;
                        x=y=z=0;
                        // x, y, z
                        // 1/0/1

                        // 1의 개수
                        while(map[i][j] != '\0'){
                            z++;
                            j--;
                        }
                        // 0의 개수
                        while(map[i][j] == '\0'){
                            y++;
                            j--;
                        }
                        // 1의 개수
                        while(map[i][j] != '\0'){
                            x++;
                            j--;
                        }
                        // 0의 개수
                        while(map[i][j] == '\0'){
                            j--;
                            // 맨 왼쪽은 쭉 null 문자만 나오므로 인덱스가 0에 도달하게 되면 탈출
                            if(j < 0)
                                break;
                        }
                        j++;

                        // 제일 작은 값 찾아서 나누기
                        int min = x;
                        if(min > y)
                            min = y;
                        if(min > z)
                            min = z;
                        x /= min;
                        y /= min;
                        z /= min;

                        // 찾은 숫자 쓰기
                        code[codeLen--] = num[x-1][y-1][z-1];

                        // 7개를 모두 찾음
                        if(codeLen == -1){
                            // 검증 코드 구하기
                            int odd = 0;
                            int even = 0;

                            for(int t=0; t<code.length; t++){
                                if(t % 2 == 0)
                                    even += code[t];
                                else
                                    odd += code[t];
                            }

                            int verificationCode = even*3 + odd;
                            if(verificationCode % 10 == 0)
                                ans += odd + even;
                            codeLen = 7;
                        }
                    }
                }
                before = input;
            }

            System.out.println("#" + test + " " + ans);
        }
        br.close();
    }

    public static void initCode(){
        for(int i=0; i<4; i++)
            for(int j=0; j<3; j++)
                for(int k=0; k<4; k++)
                    num[i][j][k] = -1;
        num[1][0][0] = 0;
        num[1][1][0] = 1;
        num[0][1][1] = 2;
        num[3][0][0] = 3;
        num[0][2][1] = 4;
        num[1][2][0] = 5;
        num[0][0][3] = 6;
        num[2][0][1] = 7;
        num[1][0][2] = 8;
        num[0][0][1] = 9;
    }

    public static int hexToDec(char ch){
        int num = 0;
        switch(ch){
            case 'A':
                num = 10;
                break;
            case 'B':
                num = 11;
                break;
            case 'C':
                num = 12;
                break;
            case 'D':
                num = 13;
                break;
            case 'E':
                num = 14;
                break;
            case 'F':
                num = 15;
                break;
            default:
                num = Character.getNumericValue(ch);
        }
        return num;
    }

    public static void makeMap(String[] temp2, int w) {
        for(int q=0; q<width; q++){
            int t = hexToDec(temp2[q].charAt(0));

            for(int k=0; k<4; k++)
                map[w][q*4 + k] = (char)hcode[t][k];
        }
    }
}