개발해요

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

문제 유형

그래프 - 다익스트라, BFS

비슷한 문제: https://programmers.co.kr/learn/courses/30/lessons/72413

풀이

문제에 오타가 좀 있고 지문이 불친절했다.

• 선택 가능한 땅의 위치: 정수 1 ~ n
• 구하고자 하는 것: 가장 가까운 친구(A, B, C) 집까지의 거리 기준 가장 먼 곳의 위치
• 가장 먼 곳이란? - 임의의 위치 X에서 A,B,C까지의 거리 중 가장 가까운 거리, 그리고 그 가까운 거리들 중 가장 먼 거리에 있는 곳
• 각 위치 ~ A,B,C의 거리 중 가장 가까운 거리를 찾아야 하므로 모든 거리는 최단거리 기준으로 생각한다. -> 다익스트라 알고리즘 사용

풀이 과정

1. A ~ (1..n), B ~ (1..n), C ~ (1..n)의 최단거리를 각각 구한다 (다익스트라 3번). -> 모든 위치마다 각 점까지의 최단거리를 구하지 않아도 된다. 그러면 시간복잡도가 O(N^2)이 된다.

2. 모든 위치마다 A,B,C까지의 거리 중 가장 짧은 거리와 장소를 계산한다. 

3. 그 중 가장 먼 거리의 장소를 구한다.

for (i in 1..n) {
    var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
    tempMinDist = min(tempMinDist, minDist[2][i])       // 그것과 i ~ C까지의 거리 비교

    // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
    if (maxOfMinDist < tempMinDist) {
        maxOfMinDist = tempMinDist
        answerLand = i
    }
}

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

data class Edge(val from: Int, val to: Int, val dist: Int)

lateinit var graph: Array<MutableList<Edge>> // 인접 리스트

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val (a,b,c) = readLine().split(" ").map(String::toInt)
    val m = readLine().toInt()
    graph = Array(n+1) { mutableListOf<Edge>() }
    val minDist = Array(3){
        IntArray(n+1) { -1 }
    } // a,b,c에서 모든 지점까지의 최단 거리

    repeat(m) {
        val st = StringTokenizer(readLine())
        val land1 = st.nextToken().toInt()
        val land2 = st.nextToken().toInt()
        val dist = st.nextToken().toInt()
        graph[land1].add(Edge(land1, land2, dist)); graph[land2].add(Edge(land2, land1, dist))
    }

    // a,b,c에서 모든 위치까지의 최단거리를 각각 구한다 (다익스트라)
    calculateMinDist(minDist[0], a)
    calculateMinDist(minDist[1], b)
    calculateMinDist(minDist[2], c)

    var maxOfMinDist = 0 // 최단 거리중 가장 먼 거리
    var answerLand = 0   // 그에 연결되는 땅 - 정답
    
    for (i in 1..n) {
        var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
        tempMinDist = min(tempMinDist, minDist[2][i])		// 그것과 i ~ C까지의 거리 비교

        // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
        if (maxOfMinDist < tempMinDist) {
            maxOfMinDist = tempMinDist
            answerLand = i
        }
    }

    println(answerLand)
}

// 다익스트라
fun calculateMinDist(minDist: IntArray, src: Int) {
    val q: Queue<Int> = LinkedList()
    q.offer(src)
    minDist[src] = 0

    while (q.isNotEmpty()) {
        val currentLand = q.poll()

        for (nextEdge in graph[currentLand]) {
            val nextDist = minDist[currentLand] + nextEdge.dist
            // 첫 방문 or 기존 거리보다 짧으면 갱신
            if (minDist[nextEdge.to] == -1 || nextDist < minDist[nextEdge.to]) {
                minDist[nextEdge.to] = nextDist
                q.offer(nextEdge.to)
            }
        }
    }
}

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

프로세스

1. 재귀(백트래킹)를 사용해서 9에서 오른쪽 or 0에서 왼쪽으로 감소/증가 하는 방향으로 감소하는 수를 모두 구한다.
2. 오름차순으로 정렬한다.
3. n > 1023이라면 -1을, 그렇지 않다면 n번째 수를 출력한다.

풀이

처음엔 앞에 있는 수로 다음 수를 구하는 것 같아서 DP를 떠올렸지만 경우의 수가 아닌 n번째 수를 구하는 방법을 생각해내지 못했다.

다음은 완전 탐색으로 풀 수 있는지 생각해본다. 수의 범위: 0 ~ 9876543210, 하지만 이 숫자를 전부 확인하면 시간 초과다. 

어떻게 해야할까

각 자릿수는 일정한 방향성을 갖는다. 왼쪽의 수가 7이라면 오른쪽에 올 수 있는 수는 6~0이다. 이 아이디어에 착안하면 재귀적으로 감소하는 수만 골라서 모두 구할 수 있다. 그리고 이것을 정렬하면 n번째 감소하는 수를 구할 수 있다.

재귀 함수의 구체적인 구현은 다음과 같다

 1. 이전 수의 마지막 자리 숫자보다 작은 수를 오른쪽에 추가해서 새로운 숫자를 구한다. -> 나머지 연산 사용

 2. 새로 구한 숫자로 재귀 함수를 호출한다

for (i in lastDigit - 1 downTo 0) {
	val newNumber = number * 10 + i  // 오른쪽에 감소하는 수 추가
	addDecreasingNumber(newNumber)
}

 3. 호출된 함수는 숫자를 감소하는 수에 추가한다

 4. 마지막 자리 수가 0이라면 재귀 함수를 종료한다.

재귀 함수 소스 코드

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

위 방식은 왼쪽에서 오른쪽으로 숫자를 추가하면서 감소하는 방향으로 수를 구하고 있다. 반대로, 오른쪽에서 증가하는 방향으로 왼쪽에 숫자를 추가하는 방식도 가능하다.

감소하는 수를 구할 수 있을지 없을지는 어떻게 판단할까?

9 8 7 6 5 4 3 2 1 0에서 9531을 도출하는 방법을 경우의 수 관점에서 생각해볼 수 있다.

9, 5, 3, 1을 선택, 8, 7, 6, 4, 2, 0은 선택하지 않는 것이다. 각 자릿수를 선택/선택하지 않는 모든 경우의 수는 2^10개이고, 모두 선택하지 않는 경우는 없기 때문에 2^10 - 1 = 1023 개가 나온다. 따라서, n > 1022라면 감소하는 수를 구할 수 없다.

코드 (Kotlin)

1. 감소하는 방향으로 백트래킹

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()

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

    if (targetIndex <= 10) {
        println(targetIndex)
    } else if (targetIndex >= 1023){ // 감소하는 수의 개수는 1023개다
        println(-1)
    } else {
        for (i in 0..9) {
            addDecreasingNumber(i.toLong())
        }
        decreasingNumbers.sort()
        println(decreasingNumbers[targetIndex])
    }
}

fun addDecreasingNumber(number: Long) {
    decreasingNumbers.add(number)

    val lastDigit = number % 10

    if (lastDigit <= 0) {
        return
    }

    for (i in lastDigit - 1 downTo 0) {
        val newNumber = number * 10 + i
        addDecreasingNumber(newNumber)
    }
}

2. 증가하는 방향 

/**
 * 1. 백트래킹으로 0 ~ 9876543210까지 감소하는 수를 구한다
 * 2. 정렬한다
 * 3. n번째 값을 출력한다
 * 4. 정수 범위에 주의한다
 */

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.pow

val decreasingNumbers = mutableListOf<Long>()
    
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val targetIndex = readLine().toInt()

    if (targetIndex <= 10) {
        println(targetIndex)
    } else {
        addDecreasingNumber(0, 0, 0)
        decreasingNumbers.sort()

        if (targetIndex > decreasingNumbers.lastIndex) {
            println(-1)
        } else {
            println(decreasingNumbers[targetIndex])
        }
    }
}

fun addDecreasingNumber(startNumber: Int, beforeLength: Int, beforeNumber: Long) {
    if (beforeLength >= 10 || startNumber >= 10) {
        return
    }

    for (i in startNumber..9) {
        val newNumber = i * (10.0).pow(beforeLength).toLong() + beforeNumber
        decreasingNumbers.add(newNumber)
        addDecreasingNumber(i + 1, beforeLength + 1, newNumber)
    }
}

https://programmers.co.kr/learn/courses/30/lessons/81303

풀이1

처음에 스택을 활용한 커서 구현 방법과 배열에 삭제 여부를 표시하는 방식을 사용해서 정확도는 통과할 수 있었지만, 효율성 테스트에서 문제가 있었다. 두 가지 방법 모두 삭제된 행을 복구할 때 O(N)이 소요됨에 따라 명령어 * 전체 행 = 약 2000억 번의 연산이 필요하기 때문이다. 커서를 움직이는 숫자의 합은 100만 이하라고 주어졌기 때문에, 복구하는데 걸리는 시간을 줄여야 효율성 테스트를 통과할 수 있다. 그리고 연결 리스트를 사용하면 O(1)으로 해결할 수 있다.

그림과 같이 연결리스트를 사용해서 삭제한 행을 스택에 저장하면, 삭제 과정이 연결리스트의 삽입과 같아진다.

그리고 항상 최근에 삭제된 행부터 복구하기 때문에, 삭제가 된 이후의 커서 이동이나 삭제는 신경쓰지 않고 이전 상태 그대로 복구할 수 있다. 단, 삭제하거나 복구할 때 양 끝의 행인지만 주의하면 된다!

풀이 2

삭제/복구 동작을 유심히 살펴보면 재밌는 사실을 발견할 수 있는데, 행을 삭제하더라도 cursor의 인덱스는 같다는 것이다.

ex)

0-1-2-3-4, cursor: 3, size: 5 

----삭제----

0-1-2-4, cursor: 3(4를 가리킴), size: 4, stack: 3

즉, cursor의 인덱스와 행의 개수만으로 차트를 표현할 수 있다. 단, 마지막 행을 삭제했을 때는 cursor -= 1을 해주어야 하는데, 이것도 실제 삭제 동작과 같다.

ex)

0-1-2-3-4, cursor: 4, size: 5

----삭제----

0-1-2-3, cursor: 4 - 1 = 3, size: 5, stack: 4

복구할 때는 행의 개수를 다시 증가시키고, 만약 현재 cursor의 인덱스가 복구하려는 행의 인덱스보다 크거나 같으면 cursor += 1을 해준다. 왜냐면 아래로 밀어야 하기 때문이다.

ex)

0-1-2-4, cursor: 3 (4를 가리킴), size: 4, stack: 3

----복구----

0-1-2-3-4, cursor: 3 + 1 = 4, size: 5

이런 풀이도 있다 정도로 알면 좋을 것 같습니다.

코드2를 참고해주세요!

코드1 (연결 리스트 사용)

import java.util.*

// 행 넘버, 위에 행, 아래 행, 삭제 여부
data class Row(val number: Int, var prev: Row? = null, var next: Row? = null, var state: Char = 'O')

class Solution {
    fun solution(n: Int, k: Int, cmd: Array<String>): String {
        val rowArray = Array<Row>(n) { i -> Row(i) }
        for (i in 0 until n-1) { // 앞으로 연결
            rowArray[i].next = rowArray[i+1]
        }
        for (i in 1 until n){    // 뒤로 연결
            rowArray[i].prev = rowArray[i-1]
        }

        var cursor = rowArray[k]
        val removeStack = Stack<Row>()

        cmd.forEach {
            when (it[0]) {
                'U' -> { 
                    val prevStep = it.split(" ")[1].toInt()
                    repeat(prevStep) {
                        cursor = cursor.prev!!
                    }
                }

                'D' -> {
                    val nextStep = it.split(" ")[1].toInt()
                    repeat(nextStep) {
                        cursor = cursor.next!!
                    }
                }

                'C' -> {
                    val removeRow = cursor
                    val prevRow = cursor.prev
                    val nextRow = cursor.next
                    removeStack.push(removeRow)
                    removeRow.state = 'X' // 삭제 표시

                    if (nextRow == null) { // 삭제될 행이 마지막 행인 경우
                        cursor = prevRow!!
                        prevRow.next = null
                    }else{
                        cursor = nextRow
                        nextRow.prev = prevRow

                        // 첫번째 행을 삭제하는 경우를 고려하지 않으면 NullPointerexception 발생
                        if (prevRow != null) prevRow.next = nextRow
                    }
                }

                else -> {
                    val removedRow = removeStack.pop()
                    val prevRow = removedRow.prev
                    val nextRow = removedRow.next
                    removedRow.state = 'O'

                    if (nextRow == null){ // 마지막 행이었던 경우
                        prevRow!!.next = removedRow
                    }else{
                        nextRow.prev = removedRow

                        if (prevRow != null) prevRow.next = removedRow
                    }
                }
            }
        }

        // 배열에 저장하지 않고 head, tail을 사용해서
        // 스택에 남아있는 행들을 다시 삽입한 후
        // head부터 순서대로 출력할 수도 있습니다.
        val answer = StringBuilder()
        rowArray.forEach {
            answer.append(it.state)
        }

        return answer.toString()
    }
}

코드2 (cursor랑 size로 차트 표현)

import java.util.*

class Solution {
    fun solution(n: Int, k: Int, cmd: Array<String>): String {
        var cursor = k
        var size = n
        val removeStack = Stack<Int>()

        cmd.forEach {
            when (it[0]) {
                'U' -> {
                    val step = it.split(" ")[1].toInt()
                    cursor -= step
                }
                'D' -> {
                    val step = it.split(" ")[1].toInt()
                    cursor += step
                }
                'C' -> {
                    removeStack.push(cursor)
                    size -= 1
                    if (cursor == size) cursor--
                }
                else -> {
                    val comebackRow = removeStack.pop()
                    size += 1
                    if (comebackRow <= cursor) cursor++
                }
            }
        }

        val answer = StringBuilder()
        for (i in 0 until size) answer.append('O') // 살아있는 행 먼저 표시
        
        while (removeStack.isNotEmpty()) {
            val removedRow = removeStack.pop()     // 연결리스트의 삽입과 같다
            answer.insert(removedRow, 'X')
        }

        return answer.toString()
    }
}

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

풀이

크게 2가지의 풀이 법이 있다. 그 중 좀 더 쉬운 방법이 분할 정복법인데, 그것도 아이디어를 떠올리기가 쉽지 않은 것 같다. 그래서 다른 분들의 풀이와 코드를 많이 참고했다.

먼저, 수가 최대 50만개라서 버블 소트를 쓰면 시간 초과가 난다.

각 숫자가 몇 번 swap 되는지를 그림으로 알아보면 다음과 같다.

각 숫자의 교점의 합이 총 swap의 합이 된다. 그리고 각 숫자의 교점의 개수는 자신보다 오른쪽에 있는 숫자들 중 더 작은 수의 개수가 된다. 예를 들어, 위의 6은 1, 3, 5 => 3번 swap 한다.

그러면 어떻게 O(n^2)보다 빠르게 각 숫자들의 오른쪽을 탐색할 수 있을까? Merge Sort를 하면 merge sort의 시간 복잡도인 O(n * log^n) 안에 가능하다.

위의 그림은 merge sort를 하는 과정에서 가장 작은 0을 정렬한 다음 상황이다.

이제 왼쪽에서 가장 작은 2와 오른쪽에서 가장 작은 1 중 더 작은 값을 정렬해야 한다. 오른쪽 값이 더 작기 때문에 1을 정렬한다. 그리고 그 과정에서 1이 2,4,6,8과 교차되는 것을 알 수 있다. 즉, 1은 2, 4, 6, 8과 swap이 되고, swap += (왼쪽 배열 개수 - 왼쪽 인덱스)와 같은 방식으로 swap 횟수를 계산할 수 있다. 이러한 과정은 오른쪽 최소 값이 왼쪽 최소값보다 작을 때마다 적용된다.

참고로 swap 횟수는 최악의 경우 대략 50만 + ... + 1 => 50만 * 50만이 될 수 있기 때문에 Long형을 사용해야 한다!

코드

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

var count = 0L
lateinit var tempArray: IntArray

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val numbers = IntArray(n) { i ->
        st.nextToken().toInt()
    }

    tempArray = IntArray(n)
    mergeSort(numbers, 0, n-1)

    print(count)
}

fun mergeSort(numbers: IntArray, start: Int, end: Int) {
    if (start == end) {
        return
    }

    val mid = (start + end) / 2
    mergeSort(numbers, start, mid)
    mergeSort(numbers, mid + 1, end)
    merge(numbers, start, end) // 정렬된 양쪽 배열을 합치면서 다시 정렬한다
}

fun merge(numbers: IntArray, start: Int, end: Int) {
    val mid = (start + end) / 2
    var left = start
    var right = mid + 1
    var tempIndex = start

    while(left <= mid && right <= end) {
        // 꼭 등호는 왼쪽이 더 작거나 같은 조건으로 붙여야 한다.
        // 그렇지 않으면 왼쪽과 오른쪽 값이 같을 때 1을 더 계산하게 된다.
        if (numbers[left] <= numbers[right]){
            // 왼쪽 값이 더 작거나 같다 -> 오른쪽 배열에 자신보다 큰 값이 없다
            tempArray[tempIndex++] = numbers[left++]
        }else{
            tempArray[tempIndex++] = numbers[right++]
            count += mid - left + 1
        }
    }

    // 왼쪽이나 오른쪽 중 남아있는 배열의 숫자 정렬
    while (left <= mid) {
        tempArray[tempIndex++] = numbers[left++]
    }
    while (right <= end) {
        tempArray[tempIndex++] = numbers[right++]
    }

    // 임시 배열에 정렬한 값을 원래 배열에 반영
    for (i in start..end) {
        numbers[i] = tempArray[i]
    }
}