Daily LeetCoding Challenge 6. Zigzag Conversion

예전에 이 문제를 봤을 땐 어떻게 풀어야 할지 몰랐었는데 오늘은 갑자기 아이디어가 떠올라서 거의 바로 풀 수 있었다! 앞으로 이런 날이 더 자주 생기면 좋겠다 😊

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

Zigzag Conversion - LeetCode

문제 설명

문자열 s와 행의 수 numRows가 주어졌을 때, 문자열 s는 numRows 행만큼 지그재그 패턴으로 쓰여있는 문자열이다. 문자열 s를 라인별로 읽은 값을 구하는 함수를 작성하라. 말로 설명하기 어려우니 예제를 보는 게 낫겠다.

 

직관

지그재그 쓰기는 두 부분으로 나눌 수 있다:
  - 세로로 쓰기
  - 아래에서 위로 대각선 방향으로 쓰기

접근법

이 솔루션에서는 지그재그 문자열을 저장하기 위해 zig 배열을 만들었다.

그리고 s의 문자 인덱스는 i, zig 배열의 열 인덱스는 c로 선언한다.
i가 s.length()보다 작을 때 다음을 수행한다:
  - r을 0부터 numRows-1까지 순회하면서 세로로 문자열을 쓴다. zig[r][c] = s.charAt(i++);
  - c를 증가시킨다. (대각선으로 쓰기 위해 열 인덱스 이동)
  - r을 numRows-2부터 1까지 순회하면서 대각선 방향으로 쓰기 zig[r][c++] = s.charAt(i++);

복잡도

시간 복잡도는 문자열 s의 길이를 n이라고 할 때, numRows x n 크기인 배열을 순회하기 때문에 O(numRows * n)이 된다. 공간 복잡도는 numRows x n 배열을 사용하기 때문에 마찬가지로 O(numRows * n)이 된다.

코드

class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        char[][] zig= new char[numRows][len];
        int c=0, i=0;
        while(i < len) {
            for(int r=0; r<numRows && i < len; r++) {
                zig[r][c] = s.charAt(i++);
            }
            c++;
            for(int r=numRows-2; r >=1 && i < len; r--) {
                zig[r][c++] = s.charAt(i++);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int r=0; r<numRows; r++) {
            for(c=0; c<len; c++) {
                if (zig[r][c] != 0) {
                    sb.append(zig[r][c]);
                }
            }
        }
        return sb.toString();
    }