[ENCODING] Encoding

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/ENCODING

algospot.com :: ENCODING

 

풀이입니다. 🤔

 

import java.util.*;
 
public class Main {
    private static final char EMPTY = 0;
    private static final Map<Character, String> binaries = new HashMap<>();
    private static final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
    static {
        char[] buffer = new char[]{'0', '0', '0', '0', '0'};
 
        // 케이스마다 문자를 이진수로 변환할 시, 중복계산을 없애기 위해 초기화 시 기록을 한다.
        binaries.put(' ', new String(buffer));
        for (char c = 'A'; c <= 'Z'; ++c) {
            int i = buffer.length - 1;
            do {
                if (buffer[i] == '0') {
                    buffer[i] = '1';
                    break;
                }
                else buffer[i--] = '0';
            } while (i >= 0);
 
            binaries.put(c, new String(buffer));
        }
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[][] board = new char[20][20];
 
        int cases = scanner.nextInt();
        for (int n = 1; n <= cases; ++n) {
            int r = scanner.nextInt(), c = scanner.nextInt(), y = 0, x = 0, directionIndex = 0;
            String line = scanner.nextLine().trim();
            for (char character : line.toCharArray()) {
                for (char digit : binaries.get(character).toCharArray()) {
                    board[y][x] = digit;
 
                    int[] direction = directions[directionIndex];
                    if (outOfBoard(y + direction[0], r)
                            || outOfBoard(x + direction[1], c)
                            || board[y + direction[0]][x + direction[1]] != EMPTY) {
                        directionIndex = (directionIndex + 1) % directions.length;
                        direction = directions[directionIndex];
                    }
                    y += direction[0];
                    x += direction[1];
                }
            }
 
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < r; ++i) {
                for (int j = 0; j < c; ++j) {
                    builder.append(board[i][j] == EMPTY ? '0' : board[i][j]);
                    board[i][j] = EMPTY;
                }
            }
 
            System.out.printf("%d %s\n", n, builder);
        }
    }
 
    private static boolean outOfBoard(int value, int max) {
        return value < 0 || value >= max;
    }
}

이 문제는 아래 문제와 짝을 이루는 문제로, 안내에 따라 문자를 Encoding 합니다. 

 

[DECODE] Decoding

주요 살펴볼 사항은 총 두가지입니다. 

 

1. 제한된 이진수 변환을 빠르게 하기 위해, 초기화 과정을 수행했습니다.

 

import java.util.*;
 
public class Main {
   static {
        char[] buffer = new char[]{'0', '0', '0', '0', '0'};
 
        // 케이스마다 문자를 이진수로 변환할 시, 중복계산을 없애기 위해 초기화 시 기록을 한다.
        binaries.put(' ', new String(buffer));
        for (char c = 'A'; c <= 'Z'; ++c) {
            int i = buffer.length - 1;
            do {
                if (buffer[i] == '0') {
                    buffer[i] = '1';
                    break;
                }
                else buffer[i--] = '0';
            } while (i >= 0);
 
            binaries.put(c, new String(buffer));
        }
    }
}

 

 

2. 나선모양으로 변경하기 위해, 4가지 방향에 대한 상대좌표를 이용하도록 하였습니다.

 

1

private static final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

cs

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️