[LeetCode] 6. Zigzag Conversion

문제

Zigzag Conversion

코드

많이 복잡한 문제는 아니었으나 삽질을 좀 해서 시간이 좀 걸렸던 문제이다.

해결 아이디어는 다음과 같다.

1. 문자열을 하나씩 돌면서 2차원 배열에 넣는다.
2. numRows 값에 해당하는 인덱스까지 넣었다면 대각선 위로 배열에 넣는다.
3. 모든 입력이 완료되면 순차적으로 print 한다.

처음에는 2차원 배열의 행의 길이를 결정하기 위해서 계산을 시도 했다. 여기에 너무 꽂혀가지고 막 이상한 수식 쓰고 그랬었는데 결론적으로 문제의 제한사항을 보고 행의 길이를 1001로 설정했다.

내 코드는 다음과 같다.

import java.util.*;
import java.io.*;

class Solution {
    public String convert(String s, int numRows) {
        boolean st = true;

        int length = s.length();
        if(numRows < 2)
            return s;
        if(length <= numRows)
            return s;

        String[][] box = new String[numRows][1001];
        int a=0;
        int b=0;
        String[] targets = s.split("");
        for(String target : targets){
            if(st){
                box[a][b] = target;
                a++;
                if(a==numRows){
                    st=false;
                    a-=2;
                }
            } else {
                box[a][++b] = target;
                a--;
                if(a==-1){
                    st=true;
                    a+=2;
                }
            }  
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<box.length;i++){
            for(int j=0;j<box[i].length;j++){
                if(box[i][j] != null){
                    sb.append(box[i][j]);
                }
            }
        }
        
        return sb.toString();
    }
}

코드가 조금 복잡하다. 다른 사람들의 풀이를 구경하면서 더 좋은 방법을 찾았다.
나처럼 2차원 배열을 사용하는 것이 아니라, List 자료형을 통해서 단순히 append 하면 대각선 위로 값을 넣는 과정과 같이 된다.

예를들어 PAYPALISHIRING 이라는 문자열을 numRows가 5인 방식으로 쓰면 다음과 같이 된다.
0번째 list -> P , H
1번째 list -> A , S , I
2번째 list -> Y , I , R
3번째 list -> P , L , I , N
4번째 list -> A , N

코드는 아래와 같다.

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

        int idx = 0, d = 1;
        List<Character>[] rows = new ArrayList[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new ArrayList<>();
        }

        for (char c : s.toCharArray()) {
            rows[idx].add(c);
            if (idx == 0) {
                d = 1;
            } else if (idx == numRows - 1) {
                d = -1;
            }
            idx += d;
        }

        StringBuilder result = new StringBuilder();
        for (List<Character> row : rows) {
            for (char c : row) {
                result.append(c);
            }
        }

        return result.toString();        
    }
}