LeetCode 6 - Zigzag Conversion

https://leetcode.com/problems/zigzag-conversion

주어진 문자열 s를 numRows에 맞게 지그재그 패턴으로 만든 다음 row별로 읽어서 합친다.

예를 들어 s = “PAYPALISHIRING”, numRows = 4 이면 output은 “PINALSIGYAHRPI”가 된다.

P     I    N
A   L S  I G
Y A   H R
P     I

규칙을 살펴보자.

나는 String [] 배열이 numRows 수만큼 존재한다고 가정하겠다.

그렇다면 배열의 크기를 정하는게 중요해지는데 numRows = 1인 경우 가장 긴 길이의 배열이 필요할 것이다.

따라서 s의 길이만큼의 배열을 생성하도록 하겠다.

문자의 할당은 어떻게 할 것인가.

문자의 할당 방식은 아래쪽 방향 이동, 오른쪽 위 대각선 방향 이동 두 가지가 존재한다.

우선은 아래 방향으로 이동하다가 최대로 이동할 수 있는 곳(numRows)에 도달하면 방향을 바꿔 오른쪽 대각선 방향 이동을 하게 하면 된다.

class Solution {

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

    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }

        int n = s.length();
        char[][] rows = new char[numRows][n];
        for (char[] row : rows) {
            Arrays.fill(row, ' ');
        }
        // 시작 위치
        int r = 0;
        int c = 0;
        int d = 0;

        for (char ch : s.toCharArray()) {

            rows[r][c] = ch;

            r += DIRECTION[d][0];
            c += DIRECTION[d][1]; 

            if (!isValidPosition(r, c, rows)) {
                r -= DIRECTION[d][0];
                c -= DIRECTION[d][1];   
                d = (d + 1) % DIRECTION.length;
                r += DIRECTION[d][0];
                c += DIRECTION[d][1]; 
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (char[] row : rows) {
            for (char ch : row) {
                if (ch != ' ') {
                    sb.append(ch);
                }
            }
        }

        return sb.toString();
    }

    private boolean isValidPosition(int r, int c, char[][] rows) {
        return r >= 0 && r < rows.length && c >= 0 && c < rows[r].length;
    }
}

 

코드를 개선해보자. 현재 낭비되는 공간이 많다.

또한 대각선 이동도 정확한 열의 위치가 필요한 것이 아니다. 단지 어느 행에 위치하는지가 중요하다.

2차원 배열이 아니라 StringBuilder 배열로 변경하면 각 row를 처리하면서 공간 낭비를 줄일 수 있다.

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }

        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        
        int currentRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows[currentRow].append(c);

            if (currentRow == 0 || currentRow == numRows - 1) {
                // 방향 전환
                goingDown = !goingDown;
            }

            currentRow += goingDown ? 1 : -1;
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }

        return result.toString();
    }
}