LeetCode Zigzag Conversion (JavaScript)

링크 : https://leetcode.com/problems/zigzag-conversion/submissions/1831172963/

문제 설명

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

---

문제 풀이

위의 문자열 길이가 14, row길이를 4라 했을 때 순서대로 진행을 해보면 첫 번째 지그재그 처럼 형태가 나온다.

즉, 3에 도달 했을 때 대각선으로 지그재그형태로 저장되기 위해 (x축 + 1, y축 - 1)을 하면서 저장해 나간다. -> y축이 0에 도달했을 때는 다시 지그재그 없이 저장될 수 있도록 로직을 구성하면 된다.

 

위와같은 형태로도 문제가 해결이 되지만 좀 더 쉽게 접근해보면 2번 째 지그재그 형태(문자열을 처리하는 순서를 표시)를 보면 값이 위, 아래로만 저장되는 형태임을 볼 수 있다.

ex ) 0행 -> 1행 -> 2행 -> 3행 -> 2행 -> 1행 -> 0행 (0행 -> 0행)

즉, x, y의 좌표를 통해 계산할 필요 없이 단순히 값을 아래로 진행하면서 저장할지 위로 올라가면서 저장할지만 정해주면 된다.

이렇게 되면 numRows의 길이만큼 각 행의 배열만 생성하면 되어 2차원 배열(1번 예시)보다 공간을 효율적으로 사용할 수 있다.

1. dir_down이 true이면 아래 방향으로 저장, false면 위 방향으로 저장

2. dir_down에 따라 +1, -1로 row를 업데이트

3. row가 numRows - 1(행의 끝부분)이거나, 첫 번째(0번째)인 경우 방향을 바꾸어 저장될 수 있도록 지정

4. 최종적으로 각 행에 쌓인 데이터를 join연산자를 이용해 읽으면 됨

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    const rows = Array.from({length: numRows}, () => []);

    if (numRows === 1 || s.length <= numRows) {
        return s;
    }

    let row = 0;
    let dir_down = true; // down인 경우 아래 방향으로
    for (const word of s) {
        rows[row].push(word);

        row += dir_down ? 1 : -1;
        
        if (row === numRows - 1 || row === 0) {
            dir_down = !dir_down;
        }
    }

    return rows.map(row => row.join('')).join('');
};

 

---

결론

처음에 2차원 배열을 이용해 zigzag를 하는 로직을 세워 문제를 해결하려고 접근을 했음.

문제는 2차원 배열을 얼만큼의 크기로 지정을 하는지 계산하는게 어려움 (크게 생성하기엔 공간복잡도 효율이 떨어짐)

 

따라서, 문제를 좀 더 쉬운 관점으로 보았고 처음 생각했던 배열 크기 선언의 문제를 효율적으로 해결할 수 있게 되었다.