개발해요

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

유형

그리디, 스택

풀이

포인트

• 필요한 만큼 삭제한다 -> 삭제했을 때 수의 길이는 항상 같다.
• 가장 크게 만든다 -> 앞에 나보다 작은 수가 있으면 삭제한다.

과정

1. 스택 선언
2. 입력 숫자를 앞에서 하나씩 확인 ->
   1. 필요한 만큼 다 삭제했다 -> 스택에 숫자 추가
   2. 삭제할 게 남아있다 ->
      1. 스택 위에 지금 숫자보다 큰 수가 있다 -> 삭제
      2. 위 과정을 스택이 비어있거나, 나보다 크거나 같은 수가 있거나, 삭제를 다 끝마칠 때까지 반복한다.
3. 수가 내림차순으로 잘 정렬돼 있으면, 위 과정에서 removeCount만큼 삭제가 일어나지 않을 수도 있으므로 남은 removeCount만큼 뒤에서 삭제한다.

Ex) 1253375에서 5개 삭제

- loop 0)

앞에 숫자가 없다. '1' 추가 (answer: 1)

- loop 1)

'1' < '2' => '1' 삭제, '2' 추가 (answer: 2)

- loop 2)

'2' < '5' =>  '2' 삭제, '5' 추가 (answer: 5)

- loop 3)

'5' > '3' =>  '3' 추가 (answer: 53)

- loop 4)

'3' == '3' =>  '3' 추가 (answer: 533)

- loop 5)

'3' < '7' =>  '3' 삭제 (answer: 53),

'3' < '7' => '3' 삭제, '7' 추가 (answer: 57)

- loop 6)

'7' > '5' => '5' 추가

- 예외 처리

삭제할 게 하나 남았으므로, 뒤에서 하나를 삭제한다.

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var (_, removeCount) = readLine().split(" ").map(String::toInt)
    val strNumber = readLine()
    val answer = StringBuilder() // 스택으로 활용

    for (num in strNumber) {
        if (removeCount == 0) {
            answer.append(num)
            continue
        }

        // 감히 나보다 작은 녀석이 앞에 있어!? -> 삭제로 응징한다
        // 나보다 큰 행님 or 같은 애가 앞에 있다 -> ㅇㅋ 인정
        while (answer.isNotEmpty() && answer.last() < num && removeCount > 0) {
            answer.deleteAt(answer.lastIndex)
            removeCount--
        }
        answer.append(num)
    }

    // 숫자들이 이미 내림차순으로 잘 정렬돼있으면,
    // 남아있는 removeCount만큼 뒤에서부터 삭제한다
    while (removeCount-- > 0) {
        answer.deleteAt(answer.lastIndex)
    }
    print(answer)
}

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

유형

누적합, Map 자료구조

풀이 과정

1. 누적합을 저장할 배열(accSum[])과 각 누적합의 개수를 카운트 할 Map(accSumMap)을 선언한다.
2. 누적합을 모두 구한다.
3. 누적합을 차례대로 확인한다. (accSum[1..n])
   1. 누적합(accSum[i])이 k(target)와 일치하면 정답 카운트를 증가시킨다
   2. accSum[i]에서 뺀 값이 k가 되는 누적합의 개수 즉, 앞에서 기록했던 누적합 카운트에서 accSumMap[accSum[i] - k]의 개수만큼 정답 카운트를 증가시킨다. (answer += accSumMap[accSum[i] - k])
   3. accSumMap에 accSum[i]의 개수를 반영한다. (accSumMap[accSum[i]] += 1)

코드1

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, target) = readLine().split(" ").map(String::toInt)
    val nums = IntArray(n + 1)
    val accSum = IntArray(n + 1)        // accSum[i]: nums[1] + ... + nums[i]
    val accSumMap = HashMap<Int, Int>() // 누적합의 개수 저장
    var answer = 0L

    // 누적합 계산
    val st = StringTokenizer(readLine())
    for (i in 1..n) {
        nums[i] = st.nextToken().toInt()
        accSum[i] = accSum[i - 1] + nums[i]
    }

    for (i in 1..n) {
        if (accSum[i] == target) answer++ // 0~i번째 까지의 누적합이 target과 같은지 검사

        // 앞서 저장한 누적합 중 accSum[i]에서 빼면 target이 되는 것의 개수
        val prevSumCount = accSumMap.getOrDefault(accSum[i] - target, 0)
        answer += prevSumCount
        accSumMap[accSum[i]] = accSumMap.getOrDefault(accSum[i], 0) + 1 // 누적합 개수 추가
    }

    println(answer)
}

코드2 (간결한 버전)

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, target) = readLine().split(" ").map(String::toInt)
    val nums = IntArray(n + 1)
    val accSum = IntArray(n + 1) // num[1..i]까지의 누적합 저장
    val accSumMap = HashMap<Int, Int>() // 누적합의 개수 저장
    var answer = 0L

    // 누적합 계산
    val st = StringTokenizer(readLine())
    for (i in 1..n) {
        nums[i] = st.nextToken().toInt()
        accSum[i] = accSum[i - 1] + nums[i]
    }

    accSumMap[0] = 1 // accSum[i] == target인 경우를 대비
    for (i in 1..n) {
        // 앞서 저장한 누적합 중 accSum[i]에서 빼면 target이 되는 것의 개수를 더한다
        answer += accSumMap.getOrDefault(accSum[i] - target, 0)
        accSumMap[accSum[i]] = accSumMap.getOrDefault(accSum[i], 0) + 1
    }

    println(answer)
}

피드백

배열에 음,양수가 함께 있을 때는 특정 부분합을 찾기 위한 알고리즘으로 투포인터를 사용하지 않는다. 왜냐하면, 포인터를 움직였을 때 합이 증가할지 감소할지 알 수 없기 때문이다.  

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)
    }
}