LeetCode 6. Zigzag Conversion

문제 링크

제한시간: 15분
2회차 제한시간: 10분

문제 접근

문제 설명이 단순하여 약간 당황했다. 그러나 numRows를 n * n 행렬로 이해하니
실마리가 보였다. 글자를 위에서부터 아래로 내려간 뒤, 마지막 행에서 오른쪽으로
+1 하며 올라온다. 행렬에 고정된 크기의 글자를 배치한 뒤, 마지막엔 왼쪽부터
오른쪽으로 0번째 행부터 n-1행까지 단어를 재조합한다. 재밌는 애너그램 암호화
방식으로 생각했다. 하지만 코딩 테스트의 답변으론 지나치게 코드가 장황했다.
결국 시간 안에 풀지 못하고 답안을 확인했다. 오랜만에 다시 풀어보려니 쉽지
않았으나, 확실히 재밌다.

풀이

2회차

5분 동안 제한시간을 두고 기억나는 대로 풀었다. 시간 차를 두고 다시 풀면 느낌이 다르다.
답이 떠오르지 않아 5분 이후 틀린 코드를 물어본 뒤 해설을 참조했다. 그 이후 다시 5분의 제한 시간동안 풀었다.
해설을 그대로 복사-붙여넣거나 암기하려 하지 않고, 읽은 것을 이해한 대로 단기 기억에 의존하여 풀었다.
조금 더 핵심적인 로직에 집중할 수 있게 된다. 역시 자료 형태가 모든 걸 결정한다는 생각이 들었다.

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

var convert = function (s, numRows) {
  if (numRows === 1) return s;
  /** @desc 맵. 사실상 2차 배열같지만 원칙적으로 1차 배열이다. 문자열의 성질을 배열처럼 활용한다. */
  const map = Array.from({ length: numRows }, () => "");
  let goingUp = -1, // 아주 중요한 변수명과 값이다. -1, 디폴트로 row의 움직임 방향은 '올라가지 않는다'.
    rowCur = 0; // goingUp을 row 내려가는 방향. 이 문제에서 꼭 필요한 것은 goingUp과 행번호를 가리키는 인덱스이다.

  for (let i = 0; i < s.length; i++) {
    /**@desc
     *  글자 할당 부분에서 2차 배열, 행렬을 직접 사용하려던 게 착오였다. 그래서 시간 안에 못풀었다.
     *  map[rowCur][colCur] = s[i] 이렇게 할당하면 메모리에 아무것도 추가되지 않는다.
     *  map[rowCur] 자체가 원시값이 할당되어 있기 때문이고, 이것은 빈 문자열이기 때문이다.
     */
    map[rowCur] += s[i]; // 따라서 행 번호에 문자만 추가해주어야 한다.

    /** @desc 이전 답안에서 boolean 할당을 없애고 goingUp에 1, -1을 할당해 방향을 제어한다.
     * 이를 통해 공간 효율을 약간 높일 수 있다.
     * gpt 답안의 변수명 또한 혼동되어 "방향이 올라가는 지의 여부"를 나타내기 위해 goingUp으로 바꿨다.
     * 이는 기본적으로 row의 인덱는 '증가한다', '행렬의 아래로 내려간다'를 가정하는 변수명이며,
     * 행을 거슬러 올라가는 것을 나타내는 플래그로 'goingUp'이라는 변수명을 작성했다.
     * 행을 '거슬러 올라갈 때'는 rowCur이 감소한다.
     * 사실 여전히 혼동되는 감이 있다.
     */
    if (rowCur == 0 || rowCur === numRows - 1) {
      goingUp = goingUp * -1;
    }
    // s가 순차적으로 배열에 저장됨에 따라 row가 증가하거나 감소한다.
    rowCur += goingUp;
  }
  /**@example
   * numRows = 3
   * map [ 'PAHN', 'APLSIIG', 'YIR' ]
   */
  return map.join("");
};

1회차

var convert = function (s, numRows) {
  const matrix = Array.from({ length: numRows }, () => Array(numRows)); // 글자 저장 행렬
  const maxSizeIndex = numRows - 1; // 인덱스와 매트릭스 사이즈가 헷갈려 변수 할당했다
  let pointer = 0,
    dir = 1; // 위 * 아래 방향 결정과 글자 포인터.
  const stack = []; // 일반적인 dfs 방식으로 접근하고자 했다.
  stack.push([0, 0]);
  // matrix fill
  while (stack.length > 0 && pointer < s.length) {
    const [cr, cc] = stack.pop();
    // 인덱스 or 크기
    if (cc === maxSizeIndex) {
      dir = -1; // 반대 방향으로.
      // .. 여기서 시간이 초과되었다.
    }
  }
};

정답

배울 게 많은 문제여서 답안 코드에 주석으로 추가했다.
gpt 무료 모델을 사용했는데, 사실 더 좋은 답안들도 많다.
그러나 내겐 이정도 답안도 배울 게 많다.

var convert = function (s, numRows) {
  if (numRows === 1 || s.length <= numRows) return s; // 글자가 row보다 작으면 원래 순서대로 나온다.

  /** @desc 이 부분이 현명하다. 행렬을 만들면서 출력될 결과를 문자열로 곧바로 저장한다.
   * 이어지는 부분의 반복문에서 로직이 훨씬 간소화된다.
   */
  const rows = Array.from({ length: numRows }, () => "");
  let currentRow = 0; // 포인터
  let goingDown = false; // 방향 - 기존의 접근도 1, -1을 생각했으나 이 방법이 나은 것 같다.

  /** @desc  이 부분이 인상깊다. s에 반복문을 건다. */
  for (let char of s) {
    // 바로 이 부분이 아직 내 능력으론 떠올릴 수 없는 한계다.
    // 자료 구조의 중요성을 느낀다.
    rows[currentRow] += char;
    // rows ["", "", "", "", ..., ""] 1차원 배열 + 문자열(사실상 이 문제의 핵심인 연속된 데이터)을 구성한다.
    // 시공간 효율이 좋은 접근이다.
    // 방향 전환: 따라서 불필요하게 x좌표 + 1을 구현하는 로직이 추가될 필요가 없다.
    if (currentRow === 0 || currentRow === numRows - 1) {
      goingDown = !goingDown;
    }
    // 내려가거나 올라간다.
    currentRow += goingDown ? 1 : -1;
  }
  // 마지막엔 1차원 배열을 하나로 합쳐주기만 하면 끝.
  return rows.join("");
};