[Kotlin, S2] 백준 2232번 지뢰

출처: unsplash.com

지뢰(2232번)

Silver 2

#그리디 알고리즘 #정렬

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

 

문제 내용

 

 

문제 접근

지뢰를 모두 터트리는 최소 개수를 구해야 한다.

직접 터트리는 지뢰의 개수를 최소로 하려면 연쇄적으로 터지는 지뢰의 개수가 많은 곳을 위주로 터트리면 된다.

 

직접 터트리는 지뢰의 위치에서 왼쪽 방향은 오름차순으로 수가 정렬되어 있어야 하고, 오른쪽 방향은 내림차순으로 정렬되어 있어야 한다.

예를 들어 다음과 같이 지뢰가 있을 때,

1 2 5 4 3 3 6 6 2

3, 7, 8번의 지뢰를 직접 터트리면 모든 지뢰를 제거할 수 있다.

 

지뢰가 연쇄적으로 터지려면 왼쪽은 오름차순으로 중복 없이 정렬되어 있어야 하고, 오른쪽은 내림차순으로 중복 없이 정렬되어 있어야 한다.

 

오름차순이 끊기면 끊긴 부분의 이전 부분이 직접 터트릴 지뢰 번호가 된다.

지뢰 번호가 지정되면 내림차순이 끊기는 부분이 터지는 지뢰들이 될 것이다.

그리고 지뢰 번호를 해제한다. 이미 터트렸기 때문이다.

이를 반복하면 최소한으로 직접 터트려서 지뢰를 제거할 수 있을 것 같다.

 

 

문제 해결 코드

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

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    var boomIndex = -1
    var before = 0

    for (i in 0 until n) {
        val p = bf.readLine().toInt()
        if (i != 0) {
            if (boomIndex == -1 && before >= p) {
                boomIndex = i

                println(boomIndex)
            }

            if (boomIndex != -1 && before <= p) {
                boomIndex = -1
            }
        }

        before = p
        if (i == n - 1) {
            if (boomIndex == -1) println(n)
        }
    }
}

 

문제 풀이

직접 입력받으면서 처리했다.

이전 값을 저장할 변수를 생성해 첫 데이터일 때는 이전 값을 초기화해 준다.

그다음 2번째 입력부터는 지뢰 번호인 boomIndex가 지정되지 않았을 때는(-1) 내림차순을 검사한다.

내림차순이 끊기면 boomIndex를 초기화하고 바로 오름차순을 검사한다.

오름차순 검사는 내림차순과는 반대로 터트릴 지뢰 번호가 지정되면 검사한다.

오름차순이 끊기면 boomIndex를 초기값으로 변경하고 다시 내림차순 검사를 반복한다.

 

이렇게 구현하면 마지막 지뢰 빼고 직접 터트릴 지뢰를 최소로 구할 수 있다.

마지막 지뢰를 직접 터트려야 하는 경우도 있을 수 있기 때문에 터트릴 지뢰 번호가 지정되지 않았을 때만 마지막 번호를 출력한다.

 

 

문제 해결 과정

오름차순/내림차순 검사를 같이 진행하지 않아서 발생한 문제가 있다.

같이 진행하지 않으면 입력 예제 1의 연속된 6이 있는 경우를 바로 처리할 수 없어 오답이 된다.