[Kotlin, S3] 백준 2346번 풍선 터뜨리기

출처: unsplash.com

 

풍선 터뜨리기(2346번)

Silver 3

#자료 구조 #덱

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

 

문제 내용

 

 

문제 접근

입력 순서대로 풍선 안에 들어있는 종이에 적혀 있는 숫자가 입력으로 주어지고, 종이에 입력된 수만큼 이동해서 다른 풍선을 터뜨려야 한다. 종이의 숫자가 양수면 다음 번호 방향으로 움직이고, 음수면 이전 방향으로 움직인다. 터진 풍선에 쓰인 종이는 재사용하지 않는다.

입력 예제 1을 예로 들어 보면

5
3 2 1 -3 -1

1번째 풍선인 종이에 3이 적힌 풍선을 터뜨렸으면, 양수이기 때문에 4번째 풍선을 터뜨려야 한다. 4번째 풍선은 음수이기 때문에 왼쪽 방향으로 이동한다. 2까지 이동했으면 2번 이동한 것이다. 2 이전의 값인 3은 이미 터져서 사용했기 때문에 이 때는 -1로 이동한다. 풍선이 원형으로 놓여 있기 때문에 이어져 있기 때문이다.

위 과정을 반복해서 풍선을 터뜨려 준다.

 

풍선이 원형으로 놓여 있는 것을 보면 ArrayDeque를 사용하면 될 것 같다. 그런데 메모리 제한이 4MB이다. ArrayDeque를 사용하면 메모리 초과가 발생한다(경험담). ArrayDeque가 왜 시간 초과가 나는지는 질문 게시판에서는 ArrayDeque를 쓸 때 추가적인 메모리가 사용된다고 하더라.

https://www.acmicpc.net/board/view/140376

 

이럴 때는 ArrayDeque와 비슷하게 사용할 수 있는 MutableList를 사용하면 된다.

풍선 안의 종이의 양수를 저장할 변수를 만들어야 한다. 처음에는 무조건 1번째 풍선이 터지기 때문에 초기값을 0으로 설정하면 쉽게 첫 출력을 할 수 있다. 종이에 0이 적히는 경우는 없기 때문이다.

List를 ArrayDequeue처럼 활용할 것이기 때문에 출력해야 하는 값은 첫 index로 오도록 할 것이다.

출력한 결과는 삭제한다. 이를 코드로 나타내 보면 아래와 같다.

answer.append("${balloon.first().number} ")
popIndex = balloon.first().paper
balloon.removeAt(0)

balloon이 모두 빠질 때까지 반복해 주면 된다.

popIndex가 터진 풍선에 적혀있는 숫자 데이터이다.

 

<조건 1>

popIndex가 양수이면 첫 번째 값을 맨 뒤로 보내면서 순회하고, 음수이면 마지막 값을 맨 앞으로 보내면서 순회한다.

if (popIndex != 0) {
    while (rotateCnt != abs(popIndex)) {
        if (popIndex > 0) {
            val first = balloon.first()
            balloon.removeFirst()
            balloon.add(first)
        } else {
            val last = balloon[balloon.lastIndex]
            balloon.removeLast()
            balloon.add(0, last)
        }

        rotateCnt++
    }
}

rotateCnt는 움직인 횟수이다.

rotateCnt가 popIndex의 절댓값과 같을 때까지 반복한다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import kotlin.math.abs

private data class Balloon(
    val number: Int,
    var paper: Int
)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val balloon = mutableListOf<Balloon>()
    val cnt = readLine().toInt()
    val numbers = StringTokenizer(readLine())

    for (i in 0 until cnt) {
        balloon.add(Balloon(i + 1, numbers.nextToken().toInt()))
    }

    val answer = StringBuilder()
    var popIndex = 0
    while (balloon.isNotEmpty()) {
        var rotateCnt = if (popIndex > 0) 1 else 0

        if (popIndex != 0) {
            while (rotateCnt != abs(popIndex)) {
                if (popIndex > 0) {
                    val first = balloon.first()
                    balloon.removeFirst()
                    balloon.add(first)
                } else {
                    val last = balloon[balloon.lastIndex]
                    balloon.removeLast()
                    balloon.add(0, last)
                }

                rotateCnt++
            }
        }

        answer.append("${balloon.first().number} ")
        popIndex = balloon.first().paper
        balloon.removeAt(0)
    }

    println(answer)
}

 

문제 풀이

풍선의 정보를 저장할 data class를 생성해 주었다. MutableList에 사용될 것이다.

balloon list를 만들어서 입력값과 번호를 함께 구성한다.

 

rotateCnt는 양수일 때는 1로, 음수일 때는 0으로 설정한다.

그 이유는 양수인 경우에는 이전에 값이 지워지면서 1칸 앞으로 옮겨져 이미 1번 이동한 상태이기 때문에 1로 초기화해 주는 것이다. 음수인 경우에는 그게 아니기 때문에 0으로 초기화해 주는 것이다.

 

rotateCnt가 popIndex의 절댓값과 같아질 때까지 순회한다.

순회가 끝나고 첫 번째 값의 풍선 번호를 출력하고 종이에 적힌 값은 popIndex에 저장한다. 그리고 첫 번째 값을 지운다.

 

 

문제 해결 과정

메모리 제한이 4MB인 문제, mutableList 덕분에 어렵지 않게 해결했다.

index 이동을 잘 생각해야 한다. 배열을 쓰는 문제가 그렇듯 실수하기 쉬운 문제이다.

덱을 쓰는 문제인데 Kotlin으로는 ArrayDeque를 쓸 수 없는 아이러니한 문제.