[leetcode] 6. ZigZag Conversion

문제

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P      A       H      N

  A  P   L  S   I   I   G

    Y        I        R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

 

풀이

$jmp=2\times \text{numRows}-2$의 주기로 반복되는 규칙이 생긴다는 것을 캐치하자.

그러면 줄별로 주기가 $jmp$가 되고, 규칙에 맞게 순서대로 출력을 하면 끝난다.

첫줄과 마지막 줄은 $jmp$마다 1개씩, 나머지 줄은 2개씩 포함된다는 것을 캐치한다면 나머지는 구현.

 

Time Complexity : $O(n)$  

 

코드

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;
        
        string ret;
        int l=s.size(), jmp = 2*numRows-2;
        
        for(int i=0;i<numRows;i++)
        {
            for(int j=0;j+i<l; j+=jmp)
            {
                ret += s[j+i];
                if(i!=0 && i!= numRows-1 && j+jmp-i<l) ret+=s[j+jmp-i];
            }
        }
        return ret;
    }
};