리트코드 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: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

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

Input: s = "A", numRows = 1
Output: "A"

 

---

 

내 풀이

내 생각의 흐름
1. 왠지 규칙이 있을 것 같은데? ... 
2. 에이 모르겠다. 일단 무지성으로 행렬에 지그재그로 문자를 넣어보자.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
    const matrix = Array.from(Array(numRows), () => new Array(s.length))
    let row = 0, col = 0;
    let zigzag = false;
    let result = '';

    if (numRows === 1) return s;

    if (numRows === 2) {
        for (let i = 0; i < s.length; i=i+2) {
            result += s[i];
        }

        for (let i = 1; i < s.length; i=i+2) {
            result += s[i];
        }

        return result
    }

    for (let i = 0; i < s.length; i++) {
        matrix[row][col] = s[i];

        if (!zigzag) {
            row = row + 1;

            if (row === numRows) {
                zigzag = true
                row = row - 2;
                col = col + 1;
            }
        } else {
            row = row - 1;
            col = col + 1;

            if (row === 0) {
                zigzag = false
            }
        }

    }



    for (let i = 0; i < numRows; i++) {
        for (let j = 0; j < s.length; j++) {
            if (!!matrix[i][j]) {
                result += matrix[i][j]
            }
        }
    }

    return result
};

 

일단 모든 테스트 케이스는 통과했다.

하지만 시간복잡도와 공간 복잡도가 최악으로 나왔다.

 

행렬을 이용하므로 문자열의 길이(s) x 행 수(numRows) 의 공간을 차지한다. 즉, O(s * numRows)의 공간 복잡도를 가지며 최악의 경우 O(1000 * 1000)의 공간 복잡도가 된다.

 

시간 복잡도의 경우, 문자열의 길이(s)만큼 한 번의 루프를 돌리므로 O(s)가 된다.

 

---

다시 풀기

다른 사람들의 풀이를 참고해서 문제를 다시 풀었다.

지그재그를 자료구조에 표현하는 방식은 다른 이들의 풀이와 거의 동일했다.

다만 선택한 자료구조가 달랐는데 나는 인접 행렬 방식을 선택한 반면, 다른 이들은 인접 리스트 방식을 선택했다.

인접 행렬의 경우 불필요한 메모리를 차지한다. 즉, O(numRows * s) 공간을 차지했다.

하지만 인접 리스트를 쓸 경우 O(numRows * 실제 문자열)의 공간만 차지하므로 이득이다.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
    const rows = new Array(numRows).fill('') // 인접리스트를 사용한다.
    let row = 0; // 현재 행 번호
    let zigzag = false; // 진행 방향으로 true면 대각선 false면 세로 방향이다.

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

    for (let i = 0; i < s.length; i++) {
        rows[row] += s[i];

        row = zigzag ? row - 1 : row + 1;

        // 진행 방향을 변경한다.
        if (row === numRows - 1 || row === 0) zigzag = !zigzag;
    }

    return rows.reduce((acc, cur) => acc + cur, '')
};

 

최종 결과, 꽤 많이 개선했다.

또 다른 이들의 풀이를 보면 규칙성을 찾아내서 계산하던데

일단은 이정도로 만족하고 넘어가야겠다.