리트코드 - 6. Zigzag Conversion

리트코드 -  6. Zigzag Conversion

출처 - https://leetcode.com/problems/zigzag-conversion/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 문자열 "PAYPALISHIRING"이 주어진 행 수에 따라 Z자 모양으로 작성됩니다. 이 패턴을 고정 폰트로 표시하면 가독성이 더 좋아질 수 있습니다.

P        A       H       N
A   P   L  S   I    I   G
Y        I        R

그리고 이것을 행별로 읽으면 "PAHNAPLSIIGYIR"이 됩니다.

주어진 행 수에 따라 이 변환을 수행하는 코드를 작성하세요.

 

의사코드

if (numRows == 1)     s 리턴 result = new StringBuilder cycleLen = 2 * numRows - 2 반복문 시작 (numRows 크기만큼, n번째 줄을 의미)     반복문 시작 (j=0 부터, j + i < s.length()까지. j += cycleLen)         result.append(s.charAt(j + i))         if (i != 0 && i != numRows - 1 && j + cycleLen - i < s.length())             result.append(s.charAt(j + cycleLen - i))     반복문 종료 반복문 종료 result.toString() 리턴

 

풀이코드

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }

        StringBuilder result = new StringBuilder(s.length());
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < s.length(); j += cycleLen) {
                result.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < s.length()) {
                     result.append(s.charAt(j + cycleLen - i));
                }
            }
        }
        return result.toString();
    }
}

 

코드설명

문자열이 주어지면 지그재그로 나열한 다음, 맨 윗줄부터 제일 아랫줄까지 출력하는 것을 다 더하는 문제다.

아래 초기코드를 보면 List 배열을 만들어서 여기에 StringBuilder 객체를 넣고, list의 인덱스를 n번째 줄에 담는 의미로 활용했다.

그리고 맨 아래에 도달하면 방향을 바꾸어서 StringBuild에 단어를 추가하는 로직을 작성했다.

 

이렇게 해도 문제는 없지만, 조금 더 런타임을 줄이기 위해 다른 방법을 생각해 보았다.

어떻게 계산을 잘 하면 list없이, stringbuilder 한개만으로 방향을 바꾸지 않아도 해결할 수 있지 않을까?

 

1. 우선 배열이 어떤 식으로 끊어지는지 파악한다.

분명히 알파벳 N 모양으로 반복되어지고 있다.

그럼 numRows의 수만큼 끊어지느냐? 하면 그렇지 않다. 아래를 찍었다가 위를 올라가야 하기 때문이다.

그럼 어떻게 할까?

 

이렇게 생각하면 된다.

이런식으로 진행되고 있으나

 

이렇게 생각해 볼 수 있다.

 

다시 바꿔서 직관적으로 생각하면 이렇게 된다. 출발점이 맨 위와 맨 아래다.

맨 위에서 numRows -1  만큼 이동하고, 다시 반복한다.

즉, 진행되는 cycle은 ( numRows - 1 ) * 2 만큼인 것이다.

 

2. 다음으로 어떻게 StringBuilder에 담을 것인가?이다.
초기코드에서는 List를 활용하여 list의 인덱스가 곧 n번째 줄에 담는 의미였다.

이번에는 직접 StringBuilder에 담아야 하므로 규칙을 찾아야 한다.

 

먼저, 맨 윗줄과 맨 아랫줄은 cycle만큼 끊어서 순차적으로 담으면 된다.

문제는 가운데 부분이다. 위에서 아래로 진행할땐 순차적으로 담아야 하고, 아래에서 위로는 거꾸로 담아야 한다.

numRows가 5라고 가정을 해보자.

2번째 줄을 담을 때에는 두가지 모두 담아야 한다. 1만큼을 빼준 값을 더하면 된다.

3번째도 마찬가지다. 처음것 담고 2만큼 빼준 값도 더하면 된다.

4번째도 마찬가지다.

 

for (int i = 0; i < numRows; i++) {
    for (int j = 0; j + i < s.length(); j += cycleLen) {
        result.append(s.charAt(j + i));
        if (i != 0 && i != numRows - 1 && j + cycleLen - i < s.length()) {
             result.append(s.charAt(j + cycleLen - i));
        }
    }
}

이를 표현한 코드가 위의 코드다.

i는 n번째 줄을 의미하고, j는 한 사이클씩 담는 반복문이다.

i가 0부터 시작하므로 제일 첫 줄과 제일 마지막은 그냥 값을 더하면 되고,

중간인 경우 먼저 i+j 를 더하고(처음것), j + cycleLen - i (나중것)을 더해주면 된다.

 

이렇게 하면 list를 사용하지 않고도 배열을 담을 수 있게 된다.

 

런타임은 기존 5ms(66%) 에서 2~3ms(99~85%) 로 줄었다.

다만 이렇게 했을 때 코드를 이해하는 데에는 주석이 없다면 다소 어려움이 있을 것 같다.

 

추가로 StringBuilder 객체를 만들 때 메모리를 최소화화기 위해 s.length()만큼의 크기를 설정했다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        List<StringBuilder> lines = new ArrayList<>();
        boolean isDown = false;

        for (int i = 0; i < numRows; i++) {
            lines.add(new StringBuilder());
        }
        int curIdx = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            lines.get(curIdx).append(c);
            if (curIdx == 0 || curIdx == numRows - 1) {
                isDown = !isDown;
            }
            if (isDown) {
                curIdx++;
            } 
            if (!isDown) {
                curIdx--;
            }
        }

        StringBuilder result = new StringBuilder();
        for (StringBuilder line : lines) {
            result.append(line);
        }
        return result.toString();
    }
}

처음에 배열을 유동적으로 만드는 방법은 없을까 고민했는데 마땅히 떠오르지 않아 List 배열안에 StringBuilder를 넣는 방법을 생각했다. isDown이라는 boolean값을 만들어서 위 아래를 반복하여 순환하도록 했다.

 

numRows가 1일 때를 고려하지 못하여 몇 번 실패했었다가 조건을 추가하여 통과했다.

 

정리

규칙에 따른 문자열을 넣는 방법은 list를 이용하거나, 직접 로직을 작성하여 추가하는 방법이 있다.