프로그래머스 월간 코드 챌린지 시즌1 > 풍선터트리기 Kotlin 코틀린 - jimoo

https://programmers.co.kr/learn/courses/30/lessons/68646?language=kotlin 

코딩테스트 연습 - 풍선 터트리기

해설

배열의 (i+1) 번째 값들이 최후의 풍선으로 남을 수 있는지 확인해야한다.

- (i+1)번 째 풍선이 최후의 풍선으로 남을 수 있는 조건

(i+1)번 째 풍선이 왼쪽에 있는 풍선들의 최솟값보다 값이 작거나 오른쪽에 있는 풍선들의 최솟값보다 값이 작으면 무조건 최후로 남을 수 있다.

더 작은 풍선을 터트릴 수 있는 기회는 한 번 사용할 수 있습니다. 

왼쪽이나 오른쪽에 있는 풍선들의 최솟값보다 최후의 풍선 값이 더 작으면 무조건 최후의 풍선으로 남을 수 있게 됩니다. 왼쪽이나 오른쪽에 한 번 그 기회를 사용하면 되기 때문에 가능합니다.

즉, 최후의 풍선인지 확인하는 값이 왼쪽에 있는 풍선들의 최솟값보다 값이 작고 오른쪽에 있는 풍선들의 최솟값보다는 클 경우, 오른쪽에 그 기회를 한 번 쓰면됩니다. 

 

하지만 왼쪽과 오른쪽에 있는 풍선들의 최솟값보다 최후의 풍선이 더 큰 경우에는 더 작은 풍선을 (좌, 우)2번 터트려야 최후의 풍선으로 남을 수 있습니다. 따라서 최후의 풍선이 될 수 없습니다.

 

코드설명

for문으로 각 배열의 값들에 접근하면서 좌, 우에 위치한 값들의 최소값(front, end)보다 값이 작은지 확인합니다.

확인하고 작다면 최후의 풍선으로 남을 수 있다고 체크(check 배열에 1로 저장)합니다. 

그리고 그 풍선의 값을 최솟값으로 설정해줍니다. 

for문으로 배열의 크기만큼 위의 과정을 반복한 뒤, check의 값을 모두 합하면 최후의 풍선으로 남을 수 있는 풍선의 개수가 됩니다.



좌, 우에 위치한 값들의 최솟값을 저장할 변수를 front와 end로 선언합니다. 

제한사항에 보면 a의 범위는

• a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.

로 설명되어 있기 때문에 초기값은 1000000000으로 설정했습니다.

var front: Int = 1000000000
var end: Int = 1000000000

 

최후에 남을 수 있는 풍선을 저장하기 위한 배열로 check를 선언했습니다. 배열의 각 초기값은 0으로 설정했습니다.

var check = Array<Int>(a.size) {i->0}

 

이제 for문에 대한 설명입니다!!

두 번째 입출력을 예시로 들어보겠습니다.

[-16, 27, 65, -2, 58, -92, -71, -68, -61, -33]

첫 번째 for문을 실행할 때 

1. if (-16<1000000000) 라면 front = -16, check[0] = 1

2. if (-33<1000000000) 라면 end = -33, check[a.size-i-1] = 1 

을 수행하게 됩니다. 

1번은 최후의 풍선의 왼쪽에 있는 모든 풍선들의 최솟값보다 작은 값을 가지는지 체크하는 if문입니다.

2번은 최후의 풍선의 오른쪽에 있는 모든 풍선들의 최솟값보다 작은 값을 가지는지 체크하는 if문입니다.

for(i in 0 until a.size){
    if (a[i]<front){
    	front=a[i]
        check[i] = 1
    }
    if (a[a.size-i-1]<end){
        end = a[a.size-i-1]
        check[a.size-i-1] = 1
    }
}

정답 코드

class Solution {
    fun solution(a: IntArray): Int {
        var answer: Int = 0
        var front: Int = 1000000000
        var end: Int = 1000000000
        var check = Array<Int>(a.size) {i->0}
        for(i in 0 until a.size){
            if (a[i]<front){
                front=a[i]
                check[i] = 1
            }
            if (a[a.size-i-1]<end){
                end = a[a.size-i-1]
                check[a.size-i-1] = 1
            }
        }
        answer = check.sum()
        return answer
    }
}