Lv 3. 풍선 터트리기

 

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

프로그래머스

 

 

 

문제를 처음 접했을 때 어떤 규칙이 존재하는지를 길게 고민하였다.

좌 우 에서 떨어지면 떨어질수록 최소 비교횟수가 늘어나는 규칙을 찾아내었고

주어진 값이 전체 array 에서 몇 번째로 최소인가를 판단하여 풀이방법을 고민하였다.

고민이 길어지다가 왼쪽 최소, 오른쪽 최소값중 한번이라도 만족한다면 마지막으로 남을 수 있는
가능성이 존재한다는 것을 발견하였고

이를 토대로 왼쪽 최솟값 array, 오른쪽 최솟값 array를 생성하여 set에 넣어줌으로써 문제를 해결.

하지만 시간복잡도와, 공간복잡도면에서 상당히 마음에 들지 않았다.

 

 

import java.util.*;

class Solution {
    int[] leftMin,rightMin;
    
    public int solution(int[] a) {
        int answer = 0;
        int size = a.length;
        leftMin = new int[size];
        rightMin = new int[size];       
        HashSet<Integer> set = new HashSet<>();
        
        leftMin[0] = a[0];
        rightMin[0] = a[size-1];
        set.add(leftMin[0]);
        set.add(rightMin[0]);
        
        for(int i = 1 ; i < size ; i++){
            leftMin[i] = Math.min(leftMin[i-1],a[i]);
            rightMin[i] = Math.min(rightMin[i-1],a[size-i-1]);
            set.add(leftMin[i]);
            set.add(rightMin[i]);
        }

        return set.size();
    }
}

 

 

GPT에게 물어본 결과 Set을 활용한 중복제거 자료구조가 Too Much라는 피드백을

받을 수 있었고 아래와 같은 a array 를 활용 for문으로 탐색하며 왼쪽 최소값 arr와

오른쪽 최솟값 arr 중 한번이라도 만족한다면 체크해나가는 식의 

피드백 코드는 더욱 시간복잡도와 공간복잡도면에서 효율적임을 배웠다.

 

 

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int size = a.length;
        if (size <= 2) return size;  // 모든 풍선을 남길 수 있음
        
        int[] leftMin = new int[size];
        int[] rightMin = new int[size];

        // 왼쪽 최소값 계산
        leftMin[0] = a[0];
        for (int i = 1; i < size; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], a[i]);
        }

        // 오른쪽 최소값 계산
        rightMin[size - 1] = a[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            rightMin[i] = Math.min(rightMin[i + 1], a[i]);
        }

        // 생존 가능한 풍선 개수 계산
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (a[i] <= leftMin[i] || a[i] <= rightMin[i]) {
                count++;
            }
        }

        return count;
    }
}

\

 

 

 

그리하여 내코드를 위와 같은 형식으로 Set 이 아닌
a[] array를 확인하는 형식으로 수정하였고
광명을 찾을 수 있었다.

 

 

import java.util.*;

class Solution {
    int[] leftMin,rightMin;
    
    public int solution(int[] a) {
        int answer = 0;
        int size = a.length;
        leftMin = new int[size];
        rightMin = new int[size];       
                
        leftMin[0] = a[0];
        rightMin[size-1] = a[size-1];
                
        for(int i = 1 ; i < size ; i++){
            leftMin[i] = Math.min(leftMin[i-1],a[i]);
            rightMin[size-i-1] = Math.min(rightMin[size-i],a[size-i-1]);
        }
        
        for(int i = 0 ; i < size ; i++){
            if(a[i] <= rightMin[i] || a[i] <= leftMin[i])
                answer++;
        }

        return answer;
    }
}