반응형

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

 

Zigzag Conversion - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

규칙을 찾아서 풀었습니다.

예를 들어 numRows=4라면,

1행은 6칸 씩,

2행은 4칸과 2칸이 번갈아가면서,

3행은 2칸과 4칸이 번갈아가면서,

4행은 6칸 씩,

기존의 문자열에서 점프하게 됩니다.

 

즉 numRows=n이라면,

1행은 (n * 2 - 2)칸 씩,

2행은 (n * 2 - 4)칸과 2칸이 번갈아가면서,

3행은 (n * 2 - 6)칸과 4칸이 번갈아가면서,

...

n행은 (n * 2 - 2)칸 씩,

기존의 문자열에서 점프하게 됩니다.

 

numRows == 1이거나 문자열의 길이가 numRows인 경우는, 주어진 문자열 s를 즉시 반환해주었습니다.

 

위 방식으로 코드를 작성하면, n의 시간복잡도와 공간복잡도로 문제를 해결할 수 있었습니다.

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1 || s.size() <= numRows) return s;
        
        string result;
        int start = numRows * 2 - 2;
        int idx = 0, row = 0, flip = 0;
        int p[2] = {start, start};
        
        for(char ch : s) {
            result.push_back(s[idx]);
            idx += p[flip];
            flip = !flip;
            if(idx >= s.size()) {
                idx = ++row;
                if(row == numRows - 1) p[0] = p[1] = start;
                else if(row == 1) p[0] -= 2, p[1] = 2;
                else p[0] -= 2, p[1] += 2;
                flip = 0;
            }
        }
        return result;
    }
};

 

 

이중 반복문으로 정리한 코드입니다.

 

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1 || s.size() <= numRows) return s;
        
        string result;
        int start = numRows * 2 - 2;
        int idx = 0, row = 0, flip = 0;
        int p[2] = {start, start};
        while(row < numRows) {
            while(idx < s.size()) {
                result.push_back(s[idx]);
                idx += p[flip];
                flip = !flip;
            }
            idx = ++row;
            flip = 0;
            if(row == numRows - 1) p[0] = p[1] = start;
            else if(row == 1) p[0] -= 2, p[1] = 2;
            else p[0] -= 2, p[1] += 2;
        }
        return result;
    }
};

 

반응형

'Algorithm' 카테고리의 다른 글

LeetCode 8 : String to Integer (atoi)  (0) 2022.03.12
LeetCode 7 : Reverse Integer  (0) 2022.03.12
백준 15942 : Thinking Heap  (0) 2022.02.12
LeetCode 128 : Longest Consecutive Sequence  (0) 2022.02.06
백준 16987 : 계란으로 계란치기  (0) 2022.02.05

+ Recent posts