[ Top Interview 150 ] 6. Zigzag Conversion

문제

6. Zigzag Conversion

  The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

• Input : 1000자 이하 string s, 가로 줄 수 numRows
• Output : Zigzag 변형 이후 위에서부터 줄 단위로 나열한 글자들

풀이 전략

0th row P       I        N
1th row A    L S     I  G
2th row Y  A   H  R
3th row P       I

• 각 줄 구하는 방법

  • 1번째 줄 : 0 - 6 - 12 - ...
    • 0부터 시작해서 6(2 * numRows - 2)씩 증가
  • 마지막 줄 : 3 - 9 - 15 - ...
    • 3(numRows - 1)부터 시작해서 6(2 * numRows - 2)씩 증가
  • 2번째 줄 : 1 - 5 - 7 - 11
    • 1부터 시작해서 4,2가 번갈아가면서 증가
    • 일반화하면 curRows부터 시작해서 (numRows - curRows - 1) * 2, curRows * 2 가 번갈아가며 증가

• 각 줄의 문자들을 순서대로 넣어서 답을 반환

풀이

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

        char[] array = s.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        addFirstLine(array, numRows, stringBuilder);
        for (int curRows = 1; curRows < numRows - 1; curRows++) {
            addMiddleLine(array, numRows, curRows, stringBuilder);
        }
        addLastLine(array, numRows, stringBuilder);

        return stringBuilder.toString();
    }

    public void addFirstLine(char[] array, int numRows, StringBuilder sb) {
        int index = 0;
        while (index < array.length) {
            sb.append(array[index]);
            index += 2 * numRows - 2;
        }
    }

    public void addMiddleLine(char[] array, int numRows, int curRows, StringBuilder sb) {
        int index = curRows;
        int count = 0;
        while (index < array.length) {
            sb.append(array[index]);
            count++;
            index += count % 2 == 0 ? curRows * 2 : (numRows - curRows - 1) * 2;
        }
    }

    public void addLastLine(char[] array, int numRows, StringBuilder sb) {
        int index = numRows - 1;
        while (index < array.length) {
            sb.append(array[index]);
            index += 2 * numRows - 2;
        }
    }
}

다른 방법

• 각 줄마다 계산하는 것은 성능은 좋을 수 있지만 실질적으로 다른 사람이 코드를 보기 힘들다.
• 실질적으로 모양에 맞춰 char[][]를 만든다면, 성능은 떨어질 수 있으나 코드가 상대적으로 읽기 쉬워진다.

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


        char[][] matrix = new char[numRows][s.length()];

        int x = 0;
        int y = 0;
        int unitSize = (numRows - 1) * 2;
        for (int i = 0; i < s.length(); i++) {
            matrix[y][x] = s.charAt(i);
            if (i % unitSize < unitSize / 2) {
                y++;
            } else {
                y--;
                x++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char[] array : matrix) {
            for (char element : array) {
                if (element != 0) {
                    sb.append(element);
                }
            }
        }

        return sb.toString();
    }
}