개발해요

https://leetcode.com/problems/spiral-matrix/

유형

구현

풀이

달팽이 모양으로 행렬의 포인터를 이동시켜보는 문제였다.

1. 행렬에 포인터를 두고, 오른쪽, 아래, 왼쪽, 위, 오른쪽, 아래,... 의 순서로 방향을 바꿀 수 있도록 방향 배열을 설정한다.

var row = 0; var col = 0
val dRow = intArrayOf(0, 1, 0, -1)
val dCol = intArrayOf(1, 0, -1, 0)
var dir = 0

2. 방향 변경 조건 설정

현재 위치에 있는 숫자를 정답에 추가하고 우선 현재 방향대로 한 칸 이동한다. 이 때, 아래 그림과 같이 이동한 위치가 행렬의 범위를 벗어나거나 이전에 확인했던 곳이라면 이동하기 전의 위치에서 방향을 바꿔서 다시 이동한다. 

var nextRow = row + dRow[dir]
var nextCol = col + dCol[dir]
// 현재 방향대로 이동했을 때 행렬을 벗어나거나 이전에 추가했던 위치면 방향을 변경
// 101: 확인한 곳
if (nextRow !in matrix.indices || nextCol !in matrix[0].indices || matrix[nextRow][nextCol] == 101) {
    dir = (dir + 1) % 4
}
row = row + dRow[dir]
col = col + dCol[dir]

3.  2번의 과정을 반복한다. 단, 무한 루프에 빠지지 않도록 숫자를 모두 추가했으면 반복문을 빠져나온다.

answer.add(matrix[row][col])
matrix[row][col] = 101 // 해당 위치의 숫자를 추가했다는 표시
// 다 추가했으면 스탑
if (++addCount >= addLimit) {
    break
}

전체 코드

class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        // right, down, left, up
        val dRow = intArrayOf(0, 1, 0, -1)
        val dCol = intArrayOf(1, 0, -1, 0)
        var dir = 0
        var row = 0; var col = 0 // 현재 좌표
        var addCount = 0         // 추가한 숫자 개수
        val addLimit = matrix.size * matrix[0].size // 최종 추가할 개수
        val answer = mutableListOf<Int>()
        
        while (true) {
            answer.add(matrix[row][col])
            matrix[row][col] = 101 // 해당 위치의 숫자를 추가했다는 표시
            // 다 추가했으면 스탑
            if (++addCount >= addLimit) {
                break
            }
            
            var nextRow = row + dRow[dir]
            var nextCol = col + dCol[dir]
            // 현재 방향대로 이동했을 때 행렬을 벗어나거나 이전에 추가했던 위치면 방향을 변경
            if (nextRow !in matrix.indices || nextCol !in matrix[0].indices || matrix[nextRow][nextCol] == 101) {
                dir = (dir + 1) % 4
            }
            row = row + dRow[dir]
            col = col + dCol[dir]
        }
        
        return answer
    }
}

https://leetcode.com/problems/3sum-closest/

유형

투 포인터

해결 과정

- 구하고자 하는 것

정수 배열에서 세 수의 합 가운데 target에 가장 가까운 것

- 쉽게 떠올릴 수 있는 방법

완전 탐색: 삼중 반복문으로 세 수의 합을 모두 확인한다.

==> 문제: O(n^3)으로 시간 내에 해결함을 보장할 수 없다.

- 시간 복잡도 개선한 방법

1. 배열에서 하나의 숫자(num1)를 선택해서 고정한다. -> O(n)
2. 나머지 수 가운데 num1과 더했을 때 target에 가장 가까운 두 수(num2, num3)를 찾는다.
3. 1번 과정을 모든 숫자에 적용해본다.

2번에서 투 포인터 방법을 사용하면 O(n)으로 두 수를 찾을 수 있다. 따라서 위 과정을 따르기 전에 우선 배열을 정렬한다. 따라서 시간 복잡도 = nlogn(정렬) * n(1번) * n(2번) = O(n^2)

- 투 포인터 사용 과정

기준): target에 가까운 정도

정답) target에 가장 가까운 합 -> 꼭 필요한 변수

과정)

1. 포인터를 오름차순 정렬된 배열의 가장 왼쪽(start)과 오른쪽(end)에 하나씩 둔다.

2-1) if 절대값(target - answer) > 절대값(target - num1 + num2 + num3) -> 정답 갱신

2-2)

if (target > num1 + num2 + num3) -> start++

else if (target > num1 + num2 + num3) -> end--

else -> 정답: num1 + num2 + num3

3. start < end일 때까지 2번 과정 반복

코드 (Kotlin)

import kotlin.math.abs

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var answerDiffer = Int.MAX_VALUE // 절대값(target - target에 가장 가까운 합)
        var answerSum = 0 // target에 가장 가까운 합
        nums.sort() // 투 포인터로 해결하기 위해 정렬
        
        for (i in 0 until nums.size - 2) {
            var start = i + 1
            var end = nums.lastIndex
            
            while (start < end) {
                val tempSum = nums[i] + nums[start] + nums[end]
                val tempDiffer = abs(target - tempSum)
                
                // target과 차이가 더 작은 합을 발견하면 정답을 갱신
                if (tempDiffer < answerDiffer) {
                    answerDiffer = tempDiffer
                    answerSum = tempSum
                }
                
                if (tempSum > target) {
                    end--
                } else if (tempSum < target) {
                    start++
                } else {
                    return tempSum // 정답은 꼭 하나라고 했으므로 리턴
                }
            }
        }
        
        return answerSum
    }
}

피드백

투 포인터는 정렬된 배열있고 특정 기준이 있을 때, 기준에 가장 부합하는 최적의 두 수를 빠르게 찾을 때 사용할 수 있다. 이분 탐색과 조건이 아주 유사하다.