개발해요

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 문제도 좀 꾸준히 풀어야지.

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

https://www.acmicpc.net/problem/2412

유형

HashSet + BFS (이분탐색을 사용해서 그래프를 따로 만들어서 풀 수도 있다고 한다.)

풀이

완전 탐색을 가장 먼저 떠올릴 수 있다, 시작점에서 모든 경우의 수를 다 가보는 것. 최소 횟수로 T에 도달하길 원하기 때문에 다른 경우의 수에서 이미 가본 곳을 다시 가보는 건 손해 -> 시간 초과가 난다. 따라서 이미 가본 곳은 다시 가지 않도록 한다. 이렇게 완전한 BFS 풀이가 됐다.

그래프와 visited는 어떻게?

그래프는 HashSet으로 나타낼 수 있다. x,y좌표로 Pair나 문자열을 구성해서 Set에 전부 저장한다. 그러면 현재 위치에서 -2 ~ +2를 한 새로운 좌표가 그래프에 포함되는지 바로 확인할 수 있다. 따라서, visited도 HashSet으로 나타낼 수 있다.

for (dx in -2..2) {
    val nextX = x + dx
    
    for (dy in -2..2) {
        val nextY = y + dy
        val coord = Pair(nextX, nextY)
        // holes: 그래프(홈)
        if (holes.contains(coord) && visited.contains(coord).not()) {
            visited.add(coord)
            q.offer(Triple(nextX, nextY, count + 1))
        }
    }
}

BFS도중 y좌표가 T인 걸 만나면 그동안 움직인 횟수를 출력, 그렇지 못했다면 마지막에 -1을 출력해준다..!

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, targetY) = readLine().split(" ").map(String::toInt)
    val holes = HashSet<Pair<Int, Int>>()
    val visited = HashSet<Pair<Int, Int>>()
    repeat(n) {
        val st = StringTokenizer(readLine())
        holes.add(Pair(st.nextToken().toInt(), st.nextToken().toInt()))
    }

    val q: Queue<Triple<Int, Int, Int>> = LinkedList()
    q.offer(Triple(0, 0, 0))

    while(q.isNotEmpty()) {
        val (x, y, count) = q.poll()

        if (y == targetY) {
            print(count)
            return
        }

        for (dx in -2..2) {
            val nextX = x + dx
            for (dy in -2..2) {
                val nextY = y + dy
                val coord = Pair(nextX, nextY)
                if (holes.contains(coord) && visited.contains(coord).not()) {
                    visited.add(coord)
                    q.offer(Triple(nextX, nextY, count + 1))
                }
            }
        }
    }

    print(-1)
}

https://www.acmicpc.net/problem/20437

유형

Map 자료구조

풀이

구하고자 하는 것

(1) 어떤 문자를 정확히 k개 포함하는 가장 짧은 문자열의 길이,

(2) 어떤 문자를 정확히 k개 포함하면서 그 문자가 앞,끝에 있는 문자열 중 가장 긴 것의 길이

(1)의 경우에도 가장 짧으려면 맨 앞, 뒤에 해당 문자가 있어야 한다. 따라서, 앞, 뒤에 어떤 문자가 있으면서 그 문자가 k개 있는 문자열의 가장 긴 것과 가장 짧은 것의 길이를 구해야 한다. 

아이디어

문자열의 앞에서부터 문자를 확인하면서 Map이나 배열에서 그 문자의 원소에 인덱스를 추가한다.

ex) "abca"

count['a'] = {0,3}, count['b'] = {1}, count['c'] = {2}

그러다가 어떤 문자의 인덱스 개수가 k개 이상이 되면, 그 문자를 발견할 때마다 그 인덱스에서 k번째 이전의 인덱스를 빼서 문자열의 길이를 계산한다. 그리고 그것을 가장 긴 문자열과 가장 짧은 문자열의 길이와 비교해서 갱신한다. 

for (i in str.indices) {
    val letter = str[i] - 'a'
    val idxList = idxListOfLetter[letter]
    idxList.add(i)

    // 해당 문자를 k개 이상 발견했을 때
    if (idxList.size >= k) {
        val length = i - idxList[idxList.size - k] + 1=
        shortestLength = length.coerceAtMost(shortestLength)=
        longestLength = length.coerceAtLeast(longestLength)
    }
}

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t) {
        val idxListOfLetter = Array(26) { mutableListOf<Int>() } // 각 문자가 발견된 인덱스를 저장하는 리스트
        val str = readLine()
        val k = readLine().toInt()
        var shortestLength = 10_001 // k개를 포함하는 가장 짧은 문자열 길이(3번)
        var longestLength = k - 1   // k개를 포함하고 앞,끝 문자가 해당 문자인 가장 긴 문자열 길이(4번)

        for (i in str.indices) {
            val letter = str[i] - 'a'
            val idxList = idxListOfLetter[letter]
            idxList.add(i)

            // 해당 문자를 k개 이상 발견했을 때
            if (idxList.size >= k) {
                val length = i - idxList[idxList.size - k] + 1
                // 가장 짧은 길이로 갱신 (3번)
                shortestLength = length.coerceAtMost(shortestLength)
                // 첫번째와 마지막 문자가 같은 문자열 중 가장 긴 걸로 갱신 (4번)
                longestLength = length.coerceAtLeast(longestLength)
            }
        }

        if (shortestLength == 10_001) { // 갱신이 안됐다 -> 어떤 문자가 k개인 문자열이 없다
            answer.append(-1).appendLine()
        } else {
            answer.append(shortestLength).append(' ').append(longestLength).appendLine()
        }
    }

    print(answer)
}