Zigzag Conversion

문제 

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

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"
 
Write the code that will take a string and make this conversion given a number of rows:
 
string convert(string s, int numRows);
 
 
Example 1:
 
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
 
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
Example 3:
 
Input: s = "A", numRows = 1
Output: "A"
 
 
Constraints:
 
1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000

 

문제 요약

문자열이 하나 주어지고, 여러 줄에 Z(지그재그) 형태로 작성한 뒤, 행 순서대로 이어붙인 문자열을 구하는 문제이다. 

예시

문자열: "PAYPALISHIRING"
행 수: 3

지그재그

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

행별로 읽기

PAHNAPLSIIGYIR

 

아이디어

지그재그는 단순히 한 줄씩 적는 것이 아니다.

문자를 아래로 내려가다가 맨 아래에 도달하면 다시 위로 올라가는 위아래 방향 전환이 반복되는 구조다. 

방향 제어 흐름 

처음에 row = 0, 아래로 이동 

row 가 numRows -1 에 도달하면 방향을 위로 전환 

row = 0 에 도달하면 다시 아래로 

0 → 1 → 2 → ... → numRows - 1 → numRows - 2 → ... → 1 → 0 → ...

 

코드

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

시간복잡도 : O(n)

공간복잡도 : O(n) - 행 개수 만큼의 StringBuilder 필요