개발해요

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

풀이

DP로 풀 수 있을 것 같았는데 방법이 떠오르지 않아서 우선 BFS를 사용했다. 매초마다 이전 위치들에서 도착할 수 있는 모든 위치로 움직이기 때문에 가장 처음 목표지점에 도착했을 때가 최단 시간이 된다.

또한, 곱하기2로 범위를 절반씩 줄일 수 있으므로 O(log^N) 시간으로 문제를 해결할 수 있다

BFS 과정에서 당연하지만 이전에 방문했던 점은 다시 방문하지 않아야 하는데, 이전보다 시간이 더 흐른 상태에서 같은 연산을 반복하기 때문이다. 따라서 방문표시를 할 배열이 필요한데, 크기를 어느 정도로 잡아야할지 고민이 됐다. 예를 들어 50,001 (x2) -> 100,002 (-1) (-1) -> 100,000 와 같이 최대 범위를 초과했다가 마이너스로 가는 경우도 있을 것 같았기 때문이다. 

결과적으로, 50,001 (-1) -> 50,000 (x2) -> 100,000처럼 최대 범위를 넘어서는 경우보단 숫자를 먼저 몇 번 빼고 x2를 하는게 항상 더 빨리 갈 수 있다. 그리고 절반인 50,000을 기준으로 숫자가 커질수록 그 차이는 훨씬 커진다.

ex)

1. 50,004 (x2) -> 100,008 (-8) -> 100,000 ==> 9번

2. 50,004 (-4) ->  50,000 (x2) -> 100,000 ==> 6번

따라서, 방문 가능 범위를 0 ~ 100,000으로 제한해도 문제를 해결할 수 있다.

개인적으로 처음엔 여기까지 생각하지 못해서 안전하게 최대 200,000까지 방문 가능하도록 했는데, 정답을 받을 수 있었다.

이후에 궁금해서 찾아봤는데, 최대 범위를 넘어서는 경우가 없는건 k의 최대 값이 짝수이기 때문이었다.

9 -> 15  ==>  9 -> 8 ->16 -> 15 의 케이스처럼, 최대 값이 홀수라면 최대 값을 넘어서고 마이너스로 가는 케이스가 존재할 수 있기 때문이다.

하지만 처음 문제를 풀 땐 생각하기 어려울 수 있기 때문에, 그럴 땐 범위를 충분히 안전하게 설정해서 푸는 게 좋을 것 같다.     

코드

import java.io.*
import java.util.*

// 250_000을 이상인 모든 수 n은
// (n * 2) 이후 -1씩 계산해주는 것보다
// -1을 먼저 몇 번 빼고 n * 2를 하는 게 항상 더 빠르다
// ex) 250_001 * 2 = 500_002 -> 500_000 ==> 3번 계산
// ex) 250_001 -> 250_000 -> 500_000 ==> 2번 계산
// 250_001에서 수가 커질 수록 차이는 더 커진다.
const val MAX_POSITION = 100_000

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val myPosition = input[0].toInt()
    val goal = input[1].toInt()

    val visited = BooleanArray(MAX_POSITION + 1)    // 방문 처리 배열
    val queue: Queue<Pair<Int, Int>> = LinkedList() // 위치, 지난 시간
    queue.offer(Pair(myPosition, 0))
    visited[myPosition] = true

    while (queue.isNotEmpty()) {
        val pair = queue.poll()
        val position = pair.first
        val time = pair.second

        if (position == goal) { // 동생을 찾았으면 종료
            print(time)
            return
        }

        // -1을 거쳐가는 최단경로는 존재할 수 없다
        val nextPosition1 = position - 1
        if (nextPosition1 >= 0 && visited[nextPosition1].not()) {
            visited[nextPosition1] = true
            queue.offer(Pair(nextPosition1, time + 1))
        }

        // 현재 위치가 동생의 위치보다 크면 증가 연산을 할 필요가 없다.
        if (position < goal) {
            val nextPosition2 = position + 1
            // 최대 범위를 넘었다가 왼쪽으로 가는 경로보다 더 빠른 경로가 항상 존재한다.
            if (nextPosition2 <= MAX_POSITION && visited[nextPosition2].not()) {
                visited[nextPosition2] = true
                queue.offer(Pair(nextPosition2, time + 1))
            }

            val nextPosition3 = position * 2
            if (nextPosition3 <= MAX_POSITION && visited[nextPosition3].not()) {
                visited[nextPosition3] = true
                queue.offer(Pair(nextPosition3, time + 1))
            }
        }
    }
}

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

난 아무래도 기하랑 도형에 약한 것 같다. 어려웠다..ㅋㅋ 도형만 나오면 시야가 좁아진다. 

처음에 직사각형 중 3개의 작은 직사각형의 합의 곱이라고 이해하고,  '한 두 개 점을 포함하지 않으면서 최대로 직사각형을 3개 만들 수 있는 방법도 있지 않을까' 싶었다. 상식적으론 모든 점을 다 포함해야 최대 값이 나올 것 같았지만, 수학의 세계는 혹시 모르니까..

어떻게 하는 걸까 고민하다가 다시 확인해보니 직사각형을 3개로 분할하는 문제였다.

풀이

직사각형을 3개로 분할할 수 있는 모양은 6가지가 있다.

이 각각의 형태에 대해 모든 크기를 확인해보면 최대값을 구할 수 있다.  

행렬을 표현하는 방법으로는 크게 2가지가 있다. (1) 한 점과 가로,세로 길이로 표현하는 방법과 (2)왼쪽 상단과 오른쪽 하단과 같이 양 끝의 두 점으로 표현하는 방법이다. 개인적으로 정사각형일 땐 (1)이 편하고 직사각형은 (2)가 편했다.

ex) 4번째 모양

이런 식으로 구성하면 한 줄짜리 행렬처럼 해당 모양을 만들 수 없을 땐, 반복문의 start, end 크기가 역전돼서 자동적으로 반복문이 실행되지 않는다.

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    val rowSize = input[0].toInt()
    val colSize = input[1].toInt()
    val square = Array<IntArray>(rowSize) {
        val numbers = readLine()
        IntArray(colSize) { i ->
            numbers[i] - '0'
        }
    }

    val lastRowIdx = rowSize - 1
    val lastColIdx = colSize - 1
    var answer = 0L

    // III
    for (col1 in 0 until colSize - 2) {
        for (col2 in col1+1 until colSize - 1) {
            val sum1 = getSquareSum(square, 0, 0, lastRowIdx, col1)
            val sum2 = getSquareSum(square, 0, col1+1, lastRowIdx, col2)
            val sum3 = getSquareSum(square, 0, col2+1, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // =
    for (row1 in 0 until rowSize - 2) {
        for (row2 in row1 + 1 until rowSize - 1) {
            val sum1 = getSquareSum(square, 0, 0, row1, lastColIdx)
            val sum2 = getSquareSum(square, row1+1, 0, row2, lastColIdx)
            val sum3 = getSquareSum(square, row2+1, 0, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅜ
    for (row in 0 until rowSize - 1) {
        val sum1 = getSquareSum(square, 0, 0, row, lastColIdx)
        for (col in 0 until colSize - 1) {
            val sum2 = getSquareSum(square, row+1, 0, lastRowIdx, col)
            val sum3 = getSquareSum(square, row+1, col+1, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅗ
    for (row in lastRowIdx downTo 1) {
        val sum1 = getSquareSum(square, row, 0, lastRowIdx, lastColIdx)
        for (col in 0 until colSize - 1) {
            val sum2 = getSquareSum(square, 0, 0, row-1, col)
            val sum3 = getSquareSum(square, 0, col+1, row-1, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅏ
    for (col in 0 until colSize - 1) {
        val sum1 = getSquareSum(square, 0, 0, lastRowIdx, col)
        for (row in 0 until rowSize - 1) {
            val sum2 = getSquareSum(square, 0, col+1, row, lastColIdx)
            val sum3 = getSquareSum(square, row+1, col+1, lastRowIdx, lastColIdx)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    // ㅓ
    for (col in lastColIdx downTo 1) {
        val sum1 = getSquareSum(square, 0, col, lastRowIdx, lastColIdx)
        for (row in 0 until rowSize - 1) {
            val sum2 = getSquareSum(square, 0, 0, row, col-1)
            val sum3 = getSquareSum(square, row+1, 0, lastRowIdx, col-1)
            answer = max(answer, sum1 * sum2 * sum3)
        }
    }

    print(answer)
}

fun getSquareSum(square: Array<IntArray>, startRow: Int, startCol: Int, endRow: Int, endCol: Int): Long {
    var sum = 0L
    for (row in startRow..endRow) {
        for (col in startCol..endCol) {
            sum += square[row][col]
        }
    }

    return sum
}

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

풀이

골드5였는데 정말 정말 어려웠다.

지금껏 풀어봤던 문제들이랑 사고방식이 전혀 다르다는 느낌이 들었다. 구현이랑 완전 탐색 문제 경험이 부족한걸까.

처음에 그리디적으로 접근했는데 분기문이 감당이 안됐다. 브루트 포스 유형이란걸 알고나서도 어떻게 풀지 쉽게 떠오르지 않았다. 다른 분들 풀이를 참고했는데, 풀면서 멘탈이 나갔는지 처음엔 설명을 봐도 이해가 안됐다..ㅋㅋㅋ

알고나니까 컨셉은 간단했다!

버튼을 눌러서 한번에 이동할 수 있는 채널을 모두 구하는 것이다.

그러면, 모든 (이동 가능한 채널 i의 자리수) + (i에서 목표 채널 N(target)까지 거리) 중 최소 값과 100에서 N까지 +, -로 가는 거리 중 최소 값이 답이 된다.

순서

1. 고장난 버튼의 개수를 확인한다. 만약 버튼이 전부 고장났다면, +, -로 이동하는 횟수가 정답이다
2. 1개라도 고장나지 않았다면, 0 <= i <= 900,000에 대해, +, - 없이 i로 한번에 이동할 수 있는 수들을 확인한다.
3. 이동 가능한 수들의 i로 직접 버튼 클릭 + 절대값(N - i) 중 최소값을 구한다.
4. 위에서 구한 최소값과 100에서 N으로 곧장 가는 절대값(N - 100) 중 작은 값이 답이 된다. (N = 101 같은 케이스 고려)

900,000까지 탐색하는 이유는 다음과 같다.

문제가 원하는 답은 아래 3가지 경우 중 최소값이다

1. 100에서 N까지 바로 가는 경우
2. 100에서 i <= N인 i를 거쳐 가는 경우 (왼쪽에서 오른쪽)
3. 100에서 i > N인 i를 거쳐 가는 경우(오른쪽에서 왼쪽) 

그리고 2, 3번의 경우

• 왼쪽에서 오른쪽으로 가는 최대 횟수는 N = 500,000이고 고장나지 않은 버튼이 0인 경우의 100 -> 500,000인 499,900번,
• 오른쪽에서 왼쪽으로 가는 최대 횟수는 고장나지 않은 버튼이 0과 9인 경우의 100 -> 900,000 -> 500,000인 400,006번이다. 그 이상의 수를 확인해봤자 499,900번을 넘기 때문에 확인하지 않아도 된다.

좀 더 간단하게는 왼쪽 -> 오른쪽 최대 값이 약 50만이기 때문에 최대 숫자를 50만 + 50만 = 100만으로 설정해서,

0 <= i <= 1,000,000을 탐색할 수 있다!

코드1

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    // 버튼이 망가졌으면 true, 아니면 false
    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    // 전부 고장났으면 +, -로만 이동하는 게 정답
    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    // target = 101과 같은 경우 고려
    var minClicked = abs(target - 100)
    
    for (i in 0 until 900_000) {
        val number = i.toString()

        // i로 번호를 직접 입력해서 갈 수 있는지 확인한다.
        if (isReachable(number, broken)){
            val numberToTarget = abs(i - target) // i에서 target으로 +나-로 이동하는 횟수
            minClicked = min(minClicked, number.length + numberToTarget)
        }
    }

    print(minClicked)
}

// 각 자리수 중 하나라도 망가진 번호가 있으면 직접 거쳐갈 수 없다.
fun isReachable(target: String, broken: BooleanArray): Boolean {
    target.forEach{ ch ->
        val number = ch - '0'
        if (broken[number]) return false
    }

    return true
}

코드2 (각 자리수 확인할 때 문자열이 아닌 정수로 처리하는 버전)

import java.io.*
import java.util.StringTokenizer
import kotlin.math.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val target = readLine().toInt()
    val brokenCount = readLine().toInt()
    val broken = BooleanArray(10)

    if (brokenCount > 0){
        val st = StringTokenizer(readLine())
        repeat(brokenCount) {
            broken[st.nextToken().toInt()] = true
        }
    }

    if (brokenCount == 10 || target == 100) {
        print(abs(target - 100))
        return
    }

    var minClicked = abs(target - 100)
    for (i in 0 until 900_000) {
        val clickCount = getClickCount(i, broken)
        if (clickCount > 0){
            val iToTarget = abs(i - target)
            minClicked = min(minClicked, clickCount + iToTarget)
        }
    }

    print(minClicked)
}

fun getClickCount(target: Int, broken: BooleanArray): Int {
    var count = 0
    var targetNumber = target

    while(true) {
        val button = targetNumber % 10
        if (broken[button]) {
            return 0
        }

        count++
        targetNumber /= 10
        if (targetNumber == 0) break
    }

    return count
}

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