C++로 구현하는 지그재그 문자열 변환(Zigzag Conversion)

문자열이 "IWANTTOLEARNCODE"처럼 주어져 있다고 가정해 보겠습니다. 이 문자열을 지정된 행 수(예: n = 3)에 걸쳐 지그재그 형태로 배치하면 다음과 같은 패턴이 만들어집니다.

이제 각 행을 위에서 아래로 차례대로 읽으면 "ITECWNTLANOEAORD"라는 새로운 문자열을 얻게 됩니다.

즉, 우리는 문자열과 행의 개수를 입력으로 받아 이러한 지그재그 변환을 수행하는 함수를 작성해야 합니다.

문제 해결 접근 방법

이 문제는 실제 지그재그 이동 경로를 시뮬레이션하는 방식으로 손쉽게 해결할 수 있습니다. 단계별로 살펴보겠습니다.

1. n이 1이면 지그재그 배치가 발생하지 않으므로 문자열 s를 그대로 반환합니다.
2. 크기가 n인 문자열 배열 arr을 생성합니다. 각 원소는 해당 행에 배치될 문자들을 저장하는 버퍼 역할을 합니다.
3. 현재 행을 나타내는 row를 0으로, 이동 방향을 나타내는 down을 true로 초기화합니다.
4. i를 0부터 문자열 길이 - 1까지 반복합니다.
   • arr[row]의 끝에 s[i]를 추가합니다.
   • row가 마지막 행(b - 1)에 도달하면 down을 false로, row가 첫 번째 행(0)에 도달하면 down을 true로 설정하여 진행 방향을 전환합니다.
   • down이 true이면 row를 1 증가시키고, 그렇지 않으면 1 감소시킵니다.
5. 빈 문자열 ans를 선언한 뒤, i를 0부터 n - 1까지 반복하면서 arr[i]를 ans에 순서대로 이어 붙입니다.
6. ans를 반환합니다.

예제 코드(C++)

다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string convert(string s, int numRows);
};
string Solution::convert(string a, int b) {
   if(b == 1)return a;
   string arr[b];
   int row = 0;
   bool down = true;
   for(int i = 0; i < a.size(); i++){
      arr[row].push_back(a[i]);
      if(row == b - 1) down = false;
      else if(row == 0)down = true;
      if(down) row++;
      else row--;
   }
   string ans = "";
   for(int i = 0; i < b; i++){
      ans += arr[i];
   }
   return ans;
}
main(){
   Solution ob;
   cout << ob.convert("IWANTTOLEARNCODE", 3);
}

입력

"IWANTTOLEARNCODE"
3

출력

"ITECWNTLANOEAORD"

복잡도 분석

이 알고리즘은 문자열의 모든 문자를 정확히 한 번씩 처리하므로 시간 복잡도는 O(N)입니다. 또한 각 행별 버퍼에 문자를 저장해야 하므로 O(N)의 추가 공간이 필요합니다.