[LeetCode 6] Zigzag Conversion - 지그재그 변환

📌 문제 설명

문자열을 지그재그(Zigzag) 형태로 재배치하고, 각 행(row)을 위에서 아래로 읽은 결과를 반환하는 문제입니다.

🔹 문제 요약

• 문자열 s와 정수 numRows가 주어짐
• 문자열을 지그재그 형태로 numRows 만큼의 행에 작성
• 이후 행을 위에서 아래로 읽은 결과를 반환

🔹 예시

s = "PAYPALISHIRING", numRows = 3

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

=> 결과: "PAHNAPLSIIGYIR"

---

✅ 풀이 아이디어

🔸 흐름 요약

• 각 행에 도달할 때마다 방향을 바꾸며 문자를 할당
• curRow: 현재 행 인덱스
• goingDown: 방향 (아래로 가고 있는지 여부)
• 각 행별 문자열을 따로 모아서 마지막에 합치면 정답

🔸 시각화 예시 (numRows = 4)

s = "PAYPALISHIRING"

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

결과: "PINALSIGYAHRPI"

---

✅ TypeScript 코드

export function convert(s: string, numRows: number): string {
  if (numRows === 1 || s.length <= numRows) {
    return s;
  }

  const rows: string[] = new Array(numRows).fill("");
  let curRow = 0;
  let goingDown = false;

  for (const char of s) {
    rows[curRow] += char;
    if (curRow === 0 || curRow === numRows - 1) {
      goingDown = !goingDown;
    }
    curRow += goingDown ? 1 : -1;
  }

  return rows.join("");
}

✅ 예외 처리

• numRows가 1이거나 문자열 길이보다 크면 그대로 반환 (지그재그 적용 불필요)

반응형

---

✅ 공간 최적화 아이디어

• rows는 string[] 대신 string[][] 형태로 구현하면 성능 개선 가능

const rows: string[][] = Array.from({ length: numRows }, () => []);

for (const char of s) {
  rows[curRow].push(char);
  if (curRow === 0 || curRow === numRows - 1) goingDown = !goingDown;
  curRow += goingDown ? 1 : -1;
}

return rows.map(row => row.join("")).join("");

✅ 문자열을 직접 연결하는 대신 문자 배열을 사용해 중간 문자열 생성을 줄임

---

📈 시간 및 공간 복잡도

항목 복잡도 설명

시간 복잡도	O(N)	모든 문자를 한 번씩 순회
공간 복잡도	O(N)	결과를 저장하기 위한 배열 필요

---

🧪 테스트 예시 (Jest)

describe("LeetCode 6: Zigzag Conversion", () => {
  it("returns correct zigzag conversion for 3 rows", () => {
    expect(convert("PAYPALISHIRING", 3)).toBe("PAHNAPLSIIGYIR");
  });

  it("returns correct zigzag conversion for 4 rows", () => {
    expect(convert("PAYPALISHIRING", 4)).toBe("PINALSIGYAHRPI");
  });

  it("returns input if numRows is 1", () => {
    expect(convert("ABCD", 1)).toBe("ABCD");
  });
});

---

✅ 마무리 정리

• 문자열을 지그재그로 나눈 후 행 단위로 이어붙이기만 하면 되는 단순한 문제
• 방향 제어(위/아래) 와 행 포인터(curRow) 를 잘 사용하면 쉽게 구현 가능
• 문자열 재조합 문제의 전형적인 예시로 활용도 높음