[4월 9일] Zigzag Conversion

📙 1. 문제

Link : 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);

제한 사항

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

 

풀이 1 : 

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */

var convert = function(s, numRows) {
    const arr = Array.from(Array(numRows), () => Array(1000).fill(null));
    let nowX = 0;
    let now = 0;
    while(true){
        for(let i=0;i<numRows;i++){
            if(!s[now]) break;
            arr[i][nowX]=s[now++];
        }
        for(let i=numRows-2;i>0;i--){
            if(!s[now]) break;
            arr[i][++nowX]=s[now++];
            console.log(i,nowX)
        }
        nowX++;
        if(!s[now]) break;
    }
    let answer = '';
    for(let i=0;i<numRows;i++){
        for(let j=0;j<1000;j++){
            if(arr[i][j]!==null) answer += arr[i][j]
        }
    }
    return answer
};

• 약간 무식한 방법으로 구현하였다.
• numRows * 1000사이즈의 배열을 만들고, 실제로 배열에 그대로 넣어서 null이면 pass, 아니라면 answer에 더하는 방식으로 구현하였다.

• 시간 복잡도는 O(n), 공간 복잡도는 O(n^2)로, 효율이 좋지 않은 풀이이다.

 풀이 2 : 

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */


var convert = function (s, numRows) {
  if (s.length <= numRows || numRows < 2) return s;
  const len = s.length;
  const num = 2 * (numRows - 1);
  let res = Array(numRows).fill("");
  let tmp = 0;
  for (let i = 0; i < len; i++) {
    tmp = i % num;
    if (tmp < numRows) {
      res[tmp] += s[i];
    } else {
      res[num - tmp] += s[i];
    }
  }
  return res.join("");
};

• 우선, 사이클이 돈다는 점을 이용하였다. 사이클의 크기 num = 2*(numRows-1)이다.
• 2차원 배열을 사용하지 않고 1차원 배열을 만들어, 각 원소의 문자열에 문자를 추가하는 방식으로 구현하였다. 그렇게하면 for문을 무식하게 돌릴 필요가 없어진다. 차곡차곡 쌓이는 형태이니 이 자료형이 보다 적합하다.

• i=0~s의 길이-1까지 for문을 돌린다. tmp = i % num 즉, 사이클 단위로 끊어준다. 그리고, 그 안에서 i < numRows라면, 그렇지 않다면으로 구분해주었다. i < numRows라면 res[tmp]에 s[i]를 그대로 넣어주면 된다. 그렇지 않다면, res[num-tmp]에 s[i]를 넣어준다.

• 시간 복잡도는 O(n), 공간복잡도는 O(n)으로 상당히 효율이 좋아진 것을 볼 수 있다.

 

---

🤔 2. 느낀 점

차곡차곡 쌓을 때는 2차원 배열보다는 1차원 배열로 각 원소를 문자열을 넣어 하나씩 문자를 추가하는 방식으로 구현하면 공간 복잡도를 낮출 수 있다. 그리고, 사이클을 이용하면 시간 복잡도를 낮출 수 있다.

 

🤩 3. 한 번 더 짚고 갈 점

arr = ['a','b']['c','d'] -> arr = ['ab','cd']로 구현하면 간편한 경우가 있다. (순차적으로 쌓는 경우, 배열에서 빈 공간이 많은 경우)