LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 문자열 s, 행의 갯수 numRows
2. output: 주어진 문자열의 문자를 주어진 행의 갯수로 지그재그 배열한 후, 위 → 아래 행 순서로 문자 리턴

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

Idea

생각한 아이디어는 3가지

1. output 문자열의 idx 변화를 통해 규칙 찾기 → 실패
2. 실제 이중배열을 만들어 지그재그 배치 후 문자열 출력 → Sol1
3. 2의 이중 배열의 문자열 출력(행 별로)에서 idx 변화 규칙 찾기 → Sol2

Solution

1. 문자를 배열에 지그재그로 저장 후, 행별로 출력

   커서를 이동시키며 미리 만든 배열에 문자를 지그재그로 저장

   class Solution {
       fun convert(s: String, numRows: Int): String {
           if (numRows == 1) return s
   				// 지그재그로 저장할 배열 초기화
           val zigzag = Array(numRows) {Array(s.length){'-'} }
           var row = 0
           var col = 0
           // 커서 위치 이동
           var move = mutableListOf<IntArray>(intArrayOf(1,0), intArrayOf(-1,1))
           var moveIdx = 0
           // 지그재그로 커서를 이동시키며 문자 저장
           for (c in s) {
               zigzag[row][col] = c
               row += move[moveIdx][0]
               col += move[moveIdx][1]
               // 커서가 배열 밖으로 벗어난 경우
               if (col >= s.length || col < 0 || row >= numRows || row < 0) {
                   // 원래 이동 취소
                   row -= move[moveIdx][0]
                   col -= move[moveIdx][1]
                   // 커서 이동 방향 변경 후, 이동
                   moveIdx = ((moveIdx + 1) % 2)
                   row += move[moveIdx][0]
                   col += move[moveIdx][1]
               }
           }
           val sb = StringBuilder()
   				// 지그재그로 저장한 문자 행 별로 출력
           for (r in 0 until numRows) {
               for (c in s.indices) {
                   // 값이 있다면 문자 추가
                   if (zigzag[r][c] != '-') sb.append(zigzag[r][c])
               }
           }
           return sb.toString()
       }
   }
   

   시간 복잡도: 문자열 순회(저장) X 이중 배열 순회(출력) = n^2

   

   🚫⁉ 실제 지그재그 크기 만큼 메모리 필요

2. 지그재그 규칙에 맞춰서 출력할 인덱스 선정

   numRows에 따라서 출력할 인덱스의 규칙이 있음 → 실제 배열에 저장 없이 바로 출력

   가장 윗 행부터 문자를 규칙에 맞춰 출력

   1. 지그재그의 꼭짓점인 행에서 다음 문자의 idx 증가 → 항상 지그재그 방향 같음

      

      다음 문자까지 반대 꼭짓점을 찍고 다시 돌아와야 하므로 idx + (numRows - 1) X 2

   2. 지그재그의 중간인 행에서 다음 문자의 idx 증가 → 지그재그 방향 바뀜

      

      위를 찍고 내려오는 진행 방향 → 현재 행(row) X 2

      아래를 찍고 올라오는 진행 방향 → (numRows - 1 - row) X 2

   ⇒ 인덱스가 문자열 범위를 벗어난 경우 다음 행으로 이동

   import java.lang.StringBuilder
   
   class Solution {
       fun convert(s: String, numRows: Int): String {
           if (numRows == 1) return s
           val sb = StringBuilder()
           var fromDown = true // 지그재그가 밑에서 오는지 (방향)
           var idx = 0 // 문자열에서 index
           var row = 0 // 지그재그에서 몇번째 줄인지
           sb.append(s[idx])
           for (i in 0..s.length-2) { // 문자수만큼 반복
               if (row == 0 || row == numRows -1) { // 지그재그의 양 끝인 경우
                   idx += (numRows - 1) * 2
               } else { // 지그재그 중간 값인 경우, 지그재그 진행 방향에 따라 idx 조정
                   idx += if (fromDown) (numRows -1 - row) * 2 else row * 2
                   fromDown = !fromDown
               }
               if (idx >= s.length) { // 문자열 범위를 벗어난 경우 조정 -> 한줄 아래로
                   idx = ++row
                   fromDown = true
               }
               sb.append(s[idx])
           }
           return sb.toString()
       }
   }
   

   시간 복잡도: 문자열 순회 = n

   

Point

1. 출력된 문자열의 각 idx에서 규칙을 찾으려다 실패