본문 바로가기

Algorithm

Zigzag Conversion - leetcode

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

class Solution {
    func convert(_ s: String, _ numRows: Int) -> String {
        // 지그재그 문자를 저장할 배열
        var words: [String] = [String].init(repeating: "", count: numRows)
        // 입력받은 문자열을 배열로 변환
        let input = s.map { $0.description }
        
        // 증가할건지 감소할건지를 정하는 변수
        var sign: Bool = true
        // 지그재그 문자를 저장할 배열의 인덱스
        var index: Int = 0
        // 만약 한 줄이면 문자 그대로 리턴하고 끝냄
        if numRows == 1 {
            return s
        }
        
        for i in input {
            // 만약에 지그재그 배열 -1 이랑 인덱스랑 같으면 감소 시작
            // 인덱스가 0이면 증가 시작
            if index == numRows - 1 {
                sign = false
            } else if index == 0 {
                sign = true
            }
            
            // 증가 해야하면 지그재그[index]에 문자 추가하고 인덱스 증가
            // 감소 해야하면 지그재그[index]에 문자 추가하고 인덱스 감소
            if sign {
                words[index] += i
                index += 1
            } else {
                words[index] += i
                index -= 1
            }
        }
        // 지그재그 배열 묶어서 리턴
        return words.joined()
    }
}

PAYPALISHIRING 이런 문자를

P   A   H   N          <- 0번째
A P L S I I G          <- 1번째
Y   I   R              <- 2번째
이렇게 지그재그로 배치했을 때 첫 번째 줄 + 두 번째 줄 + 세 번째 줄 해서
PAHNAPLSIIGYIR 이렇게 재배치한 값을 리턴하는 문제

처음엔 2차원 배열로 접근할까 했는데,
지그재그 배치에서 문자가 배치된 순서를 가만 보니 규칙을 발견함.
0 1 2 1 0 1 2 1 0 1 2 1 0 ...
이런식으로 증가했다 감소했다를 반복.

그래서 sign변수를 하나 두고 매개변수 numRows랑 비교하면서 지그재그로 값을 넣어줌
그럼 words에는 ["PAHN", "APLSIIG", "YIR"] 이렇게 들어감.

이걸 묶어서 리턴함.

근데 numRows가 1인 경우 ex.(ABC, 1) 이런 경우에는 지그재그로 배치할 수가 없음.
그래서 함수 초반에 numRows가 1이면 그냥 String 그대로 리턴하게 함.

'Algorithm' 카테고리의 다른 글

Container With Most Water - leetcode  (0) 2023.10.23
Add Two Numbers - leetcode  (0) 2023.10.19