본문 바로가기
Web development/Algorithm

[LeetCode] ZigZag Conversion (javascript)

by 자몬다 2021. 5. 19.

 

"ABCDEFGHIJKLMNO" 같은 문자열이 주어졌을 때, numRows만큼의 높낮이로 글자로 지그재그를 그리고,

그 결과를 위에서부터 순서대로 읽어내려가는 문제이다.

 

s = "ABCDEFGHIJKLMNO", numRows = 6인 경우 아래와 같이 된다.

A(0) 에서 A가 문자열, 괄호 안의 0이 index

따라서 결과는 AKBJLCIMDHNEGOF여야 한다.

 

index의 간격을 살펴보면, numRows가 6일 때 

첫째줄은 10 - 10 - 10 ...

둘째줄은 8-2-8-2 ...

셋째줄은 6-4-6-4 ...

넷째줄은 4-6-4-6 ...

다섯째줄은 2-8-2-8 ...

마지막줄은 다시 10씩 차이난다.

 

 

10

8-2

6-4

4-6

2-8

10 

으로 반복됨을 알 수 있다.

어느 줄이나 반복되는 간격들의 합은 10이라는 점도 알 수 있다.

 

따라서 첫번째와 마지막 줄의 간격이자, 모든 간격들의 합(interval)은 2 * (numRows - 1) = 10

2~5번째 줄의 첫번째 간격(first)은 interval - (2 * i)

2~5번째 줄의 두번째 간격(second)은 interval - first

 

numRows만큼 반복을 돌며 제일 윗줄부터 해당하는 문자를 뽑아 결과에 더해주고 원본 배열에서는 제거한다.

간격을 이미 알고 있으므로, index를 옮겨가면서 결과값 문자열에 더해주면 된다.

 

i(반복회차)별 arr, first/second, result의 상태

 

 

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
    const len = s.length;
    let arr = s.split('');
    if (numRows === 1 || len <= numRows) return s;

    const interval = 2 * (numRows - 1);
    let result = '';
    let tempArr = Array.from(arr);
    for (let i = 0; i < numRows; i++) {
        let index = i;
        const first = interval - 2 * i;
        const second = interval - first;
        let isFirst = 1;
        while (index < len && tempArr[index]) {
            result += tempArr[index];
            arr.splice(index, 1);
            if (i === 0 || i === numRows - 1){
                index += interval;
            } else {
                index += isFirst > 0 ? first : second;
                isFirst *= -1;
            }
        }
    }
    
    return result;
};

 

 

 

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

 

 

댓글