Today's Algorithm(2018-11-05)

leetcode 6. ZigZag Conversion

제가 좋아하는 종류의 문제입니다. 별찍기나 이 문제와 같이 패턴이 있는 것을 출력하는 문제를 좋아하는 것 같아요. 그래서 재미있게 풀었습니다. 물론 효율성은.. 그닥 좋지 않았지만요.

 

이 문제의 경우 가장 빠르게 푸는 방법은 역시나 수학적인 지식을 이용하면 확실히 빠르게 풀 수 있습니다. 저의 경우는 문제에 충실하게 지그재그를 따라가면서 배열에 넣었고 그것을 출력했거든요. 근데 수학적 지식을 이용하면 지그재그 따라갈 필요없이 바로 한 줄씩 지그재그에 있는 수를 배열에 넣고 그것을 바로 출력하면 되기 때문입니다.

 

제가 풀었던 방법은 우선 패턴을 발견하는 것에서 출발합니다.

결국 저 밑으로 갔다가 대각선을 통해 올라오는 과정이 반복되는 것이거든요. 저 부분에 초점을 맞추고 Row, Column 인덱스만 잘 맞춰주면 됩니다. 그리고 더 이상 문자가 없을 때 그만두는 것까지도요! 코드는 다음과 같습니다.

class Solution {
    public String convert(String s, int numRows) {
        Queue<String> ss = new LinkedList<>(Arrays.asList(s.split("")));
        String[][] stringArr = new String[numRows][s.length()];

        int rowIndex = 0;
        int colIndex = 0;
        
        if(numRows == 1) return s;
        
        while (!ss.isEmpty()) {

            // 밑으로 쭉
            while (rowIndex < numRows - 1 && !ss.isEmpty()) {
                stringArr[rowIndex][colIndex] = ss.poll();
                rowIndex++;
            }

            if (ss.isEmpty()) break;

            // 대각선
            while (rowIndex != 0 && !ss.isEmpty()) {
                stringArr[rowIndex][colIndex] = ss.poll();
                rowIndex--;
                colIndex++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (String[] strings : stringArr) {
            for (String string : strings) {
                if (string == null) {
                    continue;
                }
                sb.append(string);
            }
        }

        return sb.toString();
    }
}

처음에 9번째 줄 없이 출력하니 '시간초과'가 발생하더라구요. 왜냐하면 numRows가 1인 경우 바로 return해주면 되는데 안하면 밑에서 패턴을 배열에 넣는 과정을 모두 해줘야하거든요. 그래서 여기서 교훈은 바로 처리할 수 있는 것들은 따로 계산과정에 접근하지 않도록 바로 return할 것!!