[LeetCode/Kotlin]Medium - 6. Zigzag Conversation

Zigzag Conversion - LeetCode

---

문제

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

---

풀이

(1) 나의 풀이법

 

풀이 접근 과정

지그재그로 단어를 저장할 새로운 배열을 처음에 만들고 그대로 출력하면 될 것이라 생각했다. 행 길이는 numRows로 주어지니까 열 길이를 측정하여 배열을 만들기로 했다.

지그재그에서 |/ 만 따져보면, numRows-1 값이 된다. (|는 1개이고, /는 numRows-2개이기 때문) s의 사이즈를 위 값으로 나누어 몫을 구하고 나머지를 이용해 남은 열 수를 구했다.

열의 길이는 s의 길이에서 |/의 열 길이를 나눈 몫과 나머지 값을 더하면 된다. 라는 식으로 접근하였다.

 

최종 소스코드

class Solution {
    fun convert(s: String, numRows: Int): String {
        val length = s.length
        var size: Int

        if (numRows == 1) return s

        if (length <= numRows) {
            size = 1
        } else if (length <= numRows*2-2) {
            size = length - numRows + 1
        } else {
            val quotient = length/(numRows-1)
            size = quotient + (numRows-2)*quotient
            if (length%(numRows-1) != 0) {
                size++
                if (length%(numRows-1)-numRows > 0) size += length%(numRows-1)-numRows
            }
        }

        val array = Array(numRows) { Array<Char?>(size) { null } }

        var x = 0
        var y = 0

        var isStraight = true

        s.forEach {
            array[x][y] = it

            if (x == 0) {
                isStraight = true
            } else if (x == numRows-1) {
                isStraight = false
            }

            if (isStraight) x++
            else {
                x--
                y++
            }
        }

        val bf = StringBuffer()

        array.forEach { chars ->
            chars.forEach {
                if (it != null) bf.append(it)
            }
        }

        return bf.toString()
    }
}

1. 지그재그로 단어를 저장할 새로운 배열을 만들기 위해 열의 크기를 구해준다.
   • 만약 numRows가 1이면 s값 return
   • 만약 s의 길이가 numRows*2-2 보다 작거나 같으면 열의 길이는 s의 길이에 numRows를 빼주고 1을 더한 값과 같다.
     • numRows*2-2는 |/ 이 모양 배열에 들어가는 글자의 개수이다. (numRows + numRows-2)
     • 이 경우에는 지그재그가 완성되지 않으므로 우선 |에 해당되는만큼의 개수를 빼준 나머지 값이 /에 해당된다. 이에 |에 해당하는 +1을 해준다.
   • 나머지 경우에는 우선 s의 길이에서 |/의 열 길이를 나눈 몫과 나머지 값을 더한 값을 열의 개수로 둔다.
     • |/에 해당하는 열의 개수는 numRows-1 이 된다. (|는 1개이고, /는 numRows-2개이기 때문)
     • 만약 s의 길이가 |/ 열의 개수에 나누어 떨어지지 않는다면
       • | 이 한 줄 더 추가되므로 +1을 해준다.
       • s의 길이를 |/ 열의 개수로 나눈 나머지에서 numRows를 뺀 값이 0보다 크다면
         • 나머지에 numRows 값을 뺀 후의 값을 열의 개수를 구하여 더해준다.
2. 1번에서 만들어진 값을 열의 개수로 갖고 이용해 numRows 값을 행의 개수로 갖는 array 배열을 만들어준다.
3. 지그재그로 array에 값을 넣는다.
   1. 변수 isStraight가 true이면 |로 이동한다.
   2. 변수 isStraight가 false이면 /로 이동한다.
   3. x의 값이 0이면 isStraight를 true로 바꿔준다.
   4. x의 값이 가장 끝 지접이면 isStraight를 false로 바꿔준다.
4. array의 값을 순서대로 stringBuffer에 넣고 return한다.

(2) 다른 풀이법

fun convert(s: String, numRows: Int): String {
    if (numRows == 1 || s.length <= numRows) {
        return s
    }

    val result = StringBuilder()
    val n = s.length
    val cycleLen = 2 * numRows - 2

    for (i in 0 until numRows) {
        var j = 0
        while (j + i < n) {
            result.append(s[j + i])
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) {
                result.append(s[j + cycleLen - i])
            }
            j += cycleLen
        }
    }

    return result.toString()
}

---

Comment

 

나는 거의 수학 문제를 풀어놨다 ㅋㅋㅋㅋ

너무 복잡한 방법으로 푼 것 같다 ㅠㅠ