6-sally0226.md

6. ZigZag Conversion

Solution 1

• 시간복잡도: O(N)

• 알고리즘 : 완전탐색

• 풀이설명

  1. numRows 크기의 string을 담을 수 있는 vector를 만듭니다.
  2. 1에서 만든 vector의 i번째 칸에 string s의 문자를 하나씩 담습니다.
     • i는 아래와 같이 지그재그로 변화함
     • 이를 위해, 숫자가 변하는 방향을 나타내는 direction을 이용 (코드 참고)
     • i를 변화시킬 때, numRows==1인 경우를 고려하지 않으므로, 해당 경우는 따로 빼둠. (코드 참고)

  0       0       0      0  
  1    1  1    1  1    1     ...
  2  2    2  2    2  2
  3       3       3
  -> 0 1 2 3 2 1 0 1 2 3 2 1 0 ...
  

  3. 모두 담고 나서, 1에서 만든 vector의 첫 string부터 끝 string까지 순서대로 이어 붙인 string이 결과값 입니다.

• 소스코드

#include <vector>

using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> zigzag(numRows,"");
        int row = 0;
        bool direction = 0; // 0:down(++), 1:up(--)
        
        if (numRows == 1)
            return s;
        for (int i=0;i<s.size();i++){
            zigzag[row].push_back(s[i]);
            if (direction==0)
                row++;
            else
                row--;
            if (row == numRows){
                row-=2;
                direction = !direction;
            }
            if (row == -1){
                row+=2;
                direction = !direction;
            }
        }
        string result="";
        for (int i=0;i<numRows;i++){
            result += zigzag[i];
        }
        return result;
    }
};