[LeetCode] Zigzag Conversion

https://leetcode.com/problems/zigzag-conversion/

Zigzag Conversion - LeetCode

우선 문제부터 간단하게 요약하면, 

 

주어진 string을 주어진 row 수만큼의 범위 내에서 지그재그로 배열을 할 때, 

이렇게 배열된 것을 row기준으로 출력하는 것이 문제입니다. 

 

간단한 예시로 

"PAYPALISHIRING" 라는 string과 3이라는 row가 주어지면,

다음과 같이 배열이 되게 되고, 

이것을 row기준으로 출력하게 되면, "PAHNAPLSIIGYIR"로 읽어지는 것입니다.

 

<Solution>

각 row에 들어오는 문자열을 저장할 vector를 구성해 두고, 주어진 문자열을 쭉 순회하면서 올바른 row에 해당하는 vector에 추가하는 형태로 구현하면 됩니다.

 

이렇게 하면 O(n) (n = 문자열의 길이) 의 시간복잡도 내에 문제를 해결할 수 있습니다. 

 

실제 구현은 아래와 같습니다.

class Solution {
public:
    string convert(string s, int numRows) {
        string returnString;
        vector<string>stringVector(numRows, "");
        
        if(numRows == 1) return s;

        int rowDir = -1, curRow = 0;

        for(int i = 0; i<s.length(); i++){
            if(curRow == 0 || curRow == numRows-1) rowDir*=(-1);

            stringVector[curRow] += s[i];
            curRow += rowDir;
        }

        for(auto &k : stringVector){
            returnString += k;
        }
        return returnString;
    }

};