개발해요

https://leetcode.com/problems/rotate-image/

문제) n x n 배열의 시계방향 90도 회전

제한 조건) 입력 외의 2차원 배열은 사용하지 않는다

풀이)

(1) 행렬을 전치(행과 열 교환)시킨다 그리고 (2) 대칭되는 열들을 교환한다. 그러면 시계방향으로 90도 회전한 모습이 된다. 이렇게 풀 수 있는 이유는 입력 배열 안에서 회전시키려면 배열 내 원소들을 교환하는 방식으로 값을 바꿔야 하는데, 전치와 대칭열 교환 모두 그렇게 동작하기 때문이다.

코드

class Solution {
    fun rotate(matrix: Array<IntArray>): Unit {
        transpose(matrix)
        reflect(matrix)
    }
    
    // 행렬 전치(행 <-> 열)
    fun transpose(matrix: Array<IntArray>) {
        for (row in 0 until matrix.lastIndex) {
            for (col in row + 1 until matrix.size) {
                val temp = matrix[row][col]
                matrix[row][col] = matrix[col][row]
                matrix[col][row] = temp
            }
        }
    }
    
    // 대칭 col 간 스위칭
    fun reflect(matrix: Array<IntArray>) {
        for (col in 0 until matrix.size / 2) {
            for (row in matrix.indices) {
                val temp = matrix[row][col]
                matrix[row][col] = matrix[row][matrix.lastIndex - col]
                matrix[row][matrix.lastIndex - col] = temp
            }
        }
    }
}

https://leetcode.com/problems/odd-even-linked-list/

풀이

문제)

• 입력: 단방향 연결리스트가 주어진다.
• 요구사항: 홀수 인덱스 노드들을 앞으로, 짝수를 뒤로 보내라
• 조건:
  1. 인덱스는 1부터 시작한다
  2. 각 그룹 안에서의 순서는 처음 입력 그대로 유지한다
  3. 공간 복잡도: O(1) -> 새 배열을 선언하지 않고 변수 몇 개만 사용 하라는 것 같다.
  4. 시간 복잡도: O(n)

아이디어)

• odd 연결리스트, even 연결리스트를 만들고, odd 연결리스트의 끝을 even 연결리스트 헤드에 연결한다.
• 새로운 연결리스트의 생성은 포인터 변수(head, tail)만 새로 생성하면 된다.
  • odd 헤드, odd 테일, even 헤드, even 테일 4개의 변수가 필요하다.

절차)

1. odd 헤드,테일이 1번째를, even 헤드,테일은 2번째 노드를 가리킨다.
2. 인덱스에 따라서 odd/even tail.next가 현재 노드를 가리키도록 바꾸고, tail도 현재 노드를 가리키도록 업데이트 한다
3. 반복문이 끝나면 각 tail.next를 null로 바꾸고, odd의 tail을 even의 head에 연결한다.

코드

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

class Solution {
    fun oddEvenList(head: ListNode?): ListNode? {
        var oddHead: ListNode? = head
        var oddTail: ListNode? = head
        var evenHead: ListNode? =  head?.next ?: null
        var evenTail: ListNode? = head?.next ?: null
        var currentNode: ListNode?  = evenTail?.next ?: null
        var idx = 3 // 현재 노드의 인덱스, 1부터 시작
      
        while (currentNode != null) {
            if (idx++ % 2 == 1) { // 홀수 인덱스
                oddTail?.next = currentNode
                oddTail = currentNode
            } else { // 짝수 인덱스
                evenTail?.next = currentNode
                evenTail = currentNode
            }
            
            currentNode = currentNode.next
        }
        
        oddTail?.next = evenHead
        evenTail?.next = null // 이걸 안해주면 노드가 홀수 개 있을 때 evenTail이 oddTail을 가리키고 있어서 연결리스트에 사이클이 생긴다.
        
        return oddHead
    }
}

https://leetcode.com/problems/product-of-array-except-self/

유형

1. 구현

2. 누적곱(?)

풀이

방법1) 나눗셈을 이용한 풀이

1. 모든 원소(nums)를 곱한 다음, 전체 곱에서 자신을 나눈 값을 저장한다. -> answer[i] = totalProduct / nums[i]

2. nums[i]가 0일 땐 나눌 수 없으니, 곱할 때 0은 제외한다.

3. 곰곰이 생각해보면 nums에 0이 2개 이상이면, answer[i]는 모두 0이다. 

4. 따라서, (1) 0이 없을 때, (2) 1개 일 때, (3) 2개 이상일 때, 3가지 케이스로 나눌 수 있다.

방법2) 누적 알고리즘을 이용한 풀이

문제에서 나눗셈을 이용하지 말라고 한다. 누적곱(?)을 사용하자.

그림으로 왜 누적곱을 사용하는지 알아보자.

알아봤다!

i번째 정답 원소 = (왼쪽에서 오른쪽 방향 누적 곱) + (자기 자신) + (오른쪽에서 왼쪽 방향 누적 곱)

--> answer[i] = leftPrefix[i - 1] + nums[i] + rightPrefix[i + 1]

나눗셈을 사용하지 않으면서 O(n)으로 해결할 수 있다.

코드1 (나눗셈 사용)

class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        var indexOfZero = - // 원소 0의 인덱스
        var product = 1     // 0을 제외한 모든 곱
        val answer = IntArray(nums.size)
        
        for (i in nums.indices) {
            // 0이 2개 이상 -> 모든 값이 0이 되기 때문에 stop
            if (nums[i] == 0 && indexOfZero != -1) {
                product = 0
                break
            } else if (nums[i] == 0 && indexOfZero == -1) { // 0을 처음 발견했을 때
                indexOfZero = i
                continue
            }
            
            product *= nums[i]
        }
        
        // 0이 하나라면, answer[indexOfZero] = 나머지 원소의 곱, 나머지는 0
        if (product != 0 && indexOfZero != -1) {
            answer[indexOfZero] = product
        } 
        // 0이 없을 때
        else if (indexOfZero == -1) {
            for (i in answer.indices) {
                answer[i] = product / nums[i]
            }
        }
        
        return answer
    }
}

코드2 (누적 알고리즘)

/**
 * answer[i] = 왼쪽누적곱[i-1] * 오른쪽누적곱[i+1]
 */
class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        val answer = IntArray(nums.size)
        val leftPreProducts = IntArray(nums.size)
        val rightPreProducts = IntArray(nums.size)
        
        leftPreProducts[0] = nums[0]
        rightPreProducts[nums.lastIndex] = nums.last()
        
        // 오른쪽 방향으로 누적곱
        for (i in 1 until nums.size) {
            leftPreProducts[i] = leftPreProducts[i-1] * nums[i]
        }
        // 끝에서 왼쪽 방향으로 누적곱
        for (i in nums.lastIndex - 1 downTo 0) {
            rightPreProducts[i] = rightPreProducts[i + 1] * nums[i]
        }
        
        for (i in 1 until answer.lastIndex) {
            answer[i] = leftPreProducts[i - 1] * rightPreProducts[i + 1]
        }
        answer[0] = rightPreProducts[1]
        answer[answer.lastIndex] = leftPreProducts[answer.lastIndex - 1]
        
        return answer
    }
}

https://leetcode.com/problems/wiggle-subsequence/

유형

DP or Greedy

과정

난이도가 medium 이었지만, 나 한정 hard였다. 신기하게도 어제는 아무리 문제를 뜯어보고 풀이를 맛봐도 알송달송했는데, 오늘은 이해가 된다.(쓰면서 알았다. 제대로 이해하진 못했다) 무의식에서 내 머리가 열심히 고생해준 것 같다ㅎ

처음 봤을 때 DP 같다는 생각이 들었다. 길이가 k인 배열에서 nums[k]를 지우냐, 지우지 않느냐에 따라서 가장 긴 wiggle sequence를 결정할 수 있을 것 같았다. 그래서 경우의 수를 따져보려고 했는데, 뭔가 복잡했다. 노트가 없었어서(^^;) 머리에서만 해결해려다 보니 그랬던 것 같다.

잘 모르겠어서 discussion을 찾아봤다. 리트 코드는 세계적으로 많은 유저들이 있어서 그런지, discussion이 활성화 돼있어서 참 좋다. 친절한 분들의 친절한 설명이 많다. 아무튼, 그런데 설명을 봐도 뭐가 뭔지 잘 모르겠다 싶었다. DP는 일반적으로 생각하는 방식과 달라서, 반대로 Greedy는 너무 직관적인 때가 많아서 어렵다는 생각이 든다. (대충 다 어렵다는 뜻)

풀이

다시 문제로 돌아와서, DP든 Greedy든 어떤 원소들은 지우는 게 항상 이득인 때가 있다. 이전 원소와 값이 같거나, positive/negative의 상태가 같을 때가 그렇다. 지우지 않으면 풀이를 종료해야 하기 때문이다. 그런데, 그런 원소들을 다 지우면 자연스럽게 Wiggle Sequence만 남는다. 값이 같거나 상태가 같은 원소를 다 지워버렸기 때문이다.

예를 들어 배열을 이전 항과의 상대적 상태로 표현했을 때 (상태: +,-,0), 000+++-+--++--- -> 0+-+-+-가 된다. 즉, 첫 원소를 제외하고 0(이전 항과 같음)은 모두 제거되고, 연속된 '+'나'-'는 하나만 남게 된다. 따라서, 이 작업만 해주면 자연스럽게 정답을 찾게 된다

그런데 조금 생각해보니까 뭔가 이상하다. 위의 예시 000+++-+--++---에서 숫자로 직접 해보면, 연속된 상태에서도 어떤 값을 지우느냐에 따라서 길이가 달라진다. 나는 이 부분을 이해하는 데 애를 먹었고, 사실 완벽하게 이해하지 못했다. 그래서 아이디어로 설명을 대신해보려고 한다. 배열 a,b,....,c,d (a<b, c>d)가 있을 때, (a,b)와 (c,d)는 b<c, b==c, b>c 상관 없이 항상 길이 3으로 연결할 수 있다.

코드

class Solution {
    fun wiggleMaxLength(nums: IntArray): Int {
        if (nums.size <= 1) {
            return nums.size
        }
        
        var answer = 1
        var prevDiff = 0
        
        for (i in 1 until nums.size) {
            val diff = nums[i-1] - nums[i]
            
            // 이전 두 수의 상태와 다른 경우
            // 등호를 통해 첫 원소와 연속해서, [5 5 5 3]처럼 처음에 같은 수들이 나오는 것도 처리할 수 있다
            if ((prevDiff >= 0 && diff < 0) || (prevDiff <= 0 && diff > 0)) {
                answer++
                prevDiff = diff
            }
        }
        
        return answer
    }
}

피드백

이해하기 어려운 부분이 DP와 관련이 있을 것 같다. DP 문제도 좀 꾸준히 풀어야지.

혼자 공부 특) 막히는 부분 해결하기 어려움ㅠㅠ