[LeetCode] 6. ZigZag Conversion

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

ZigZag Conversion - LeetCode

ZigZag Conversion - Medium

 

String이 주어졌을때, 이 String을 지그재그로 변형시킨다.

이 후, 지그재그로 된 String을 행렬 순서로 출력하였을때 나타나는 String을 출력하는 문제다.

 

지그재그 순서는 아래와 같다.

 

1				9				17 ...
2			8	10			16	18 ...
3		7		11		15		19 ...
4	6			12	14			20 ...
5				13				21 ...

이를 출력하면 1 9 17 ... 2 8 10 16 18 ... 이 될 것이다.

이를 공식화 하면 아래와 같다

 

0				2(n-1)				4(n-1)			...
1		2(n-1)-1	2(n-1)+1    4(n-1)-1		4(n-1)+1		...
2		2(n-1)-2	2(n-1)+2    4(n-1)-2		4(n-1)+2		...
n-1		...

이에 맞게 코드를 짜주면 된다.

 

전체 풀이 코드

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