[Programmers] 풍선 터트리기

문제

 

월간 코드 챌린지 시즌1 > 풍선 터트리기

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

 

 

아이디어

 

i번째에 존재하는 풍선이 최후까지 남는 지를 확인하기 위해 제가 생각한 방법은 다음과 같습니다.

 

우선 i번째를 기준으로 좌측과 우측의 풍선을 최대한 터트려서 총 3개의 풍선을 남깁니다.

 

그리고 좌측에 최후까지 남은 풍선을 i-1번째 풍선, 우측에 최후까지 남은 풍선을 i+1번째 풍선이라고 일컫겠습니다.

 

1. 만약 풍선을 3개로 만드는 과정에서 번호가 작은 풍선을 터트리지 않았다면??

• i-1번째와 i+1번째는 항상 방향마다 가장 작은 번호의 숫자가 담긴 풍선이 남음
• 그리고 i-1번째와 i+1번째 풍선 중 하나라도 i보다 번호가 큰 풍선이 있으면 i는 최후까지 남는 것이 가능

2. 만약 풍선을 3개로 만드는 과정에서 번호가 작은 풍선을 터트렸다면??

• 터트린 방향에서는 가장 큰 번호의 풍선을 남기는 것이 최적의 방법
• 터트리지 않은 방향은 당연히 가장 작은 숫자의 풍선이 남음
• 그리고 i-1번째와 i+1번째 풍선이 모두 i보다 큰 풍선이어야만 i는 최후까지 남는 것이 가능

3. 0번째 인덱스와 length-1번째 인덱스는 항상 최후까지 남기 가능

• 0번째 풍선은 1~length-1까지 비교하여 풍선을 다 터트리고 남은 풍선과 비교하면 항상 남기 가능
• length-1번째도 0~length-2까지 비교하여 풍선을 다 터트리고 남은 풍선과 비교하면 항상 남기 가능

 

위의 방법을 사용하기 위해서는 i번째까지의 최솟값과 최댓값을 저장해두는 배열이 필요합니다.

 

왜냐하면 a의 길이가 1이상 1,000,000 이하이기 때문에 O(n)으로 문제를 푸는 것이 합리적이기 때문입니다.

 

 

구현 코드 (JavaScript)

 

function solution(a) {
    let res = 0;
    const leftMin = []; // 왼쪽에서부터 지나온 값들의 최솟값 담기
    const leftMax = []; // 왼쪽에서부터 지나온 값들의 최댓값 담기
    const rightMin = []; // 오른쪽에서부터 지나온 값들의 최솟값 담기
    const rightMax = []; // 오른쪽에서 지나온 값들의 최댓값 담기
    
    // 왼쪽에서 오는 경우의 최소, 최댓값 저장
    for(let i=0; i<a.length; i++) {
        if(i === 0) {
            leftMin[i] = a[i];
            leftMax[i] = a[i];
        } else {
            leftMin[i] = Math.min(a[i], leftMin[i-1]);
            leftMax[i] = Math.max(a[i], leftMax[i-1]);
        }
    }
    
    // 오른에서 오는 경우의 최소, 최댓값 저장
    for(let i=a.length-1; i>=0; i--) {
        if(i === a.length-1) {
            rightMin[i] = a[i];
            rightMax[i] = a[i];
        } else {
            rightMin[i] = Math.min(a[i], rightMin[i+1]);
            rightMax[i] = Math.max(a[i], rightMax[i+1]);
        }
    }
    
    for(let i=0; i<a.length; i++) {
        const target = a[i];
        
        if(i === 0 || i == a.length-1) { // 양 끝은 항상 남기기 가능
            res++;
        } else {
            if(target < leftMin[i-1] || target < rightMin[i+1]) { // 작은 풍선을 터트린 적이 없을 경우, 타겟값보다 하나라도 큰 값이 있으면 됨
                res++;
            } else if(target < leftMax[i-1] && target < rightMin[i+1]) { // 왼쪽에서 작은 풍선을 터트린 적이 있는 경우, 타겟값보다 모두 커야 함
                res++;
            } else if(target < leftMin[i-1] && target < rightMax[i+1]) { // 오른쪽에서 작은 풍선을 터트린 적이 있는 경우, 타겟값보다 모두 커야 함
                res++;
            }
        }
    }
    
    return res;
}

 

 

읽어주셔서 감사합니다.