[프로그래머스/Level3] 풍선 터뜨리기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

a의 길이가 기니까 풍선 갯수(n)를 늘려가며 규칙성을 찾아보자..

 

- n이 1이면, 무조건 풍선이 하나 남으므로 1 반환

- n이 2면, 2가지(1번 풍선이 작고 2번 풍선이 큰 경우 / 1번 풍선이 크고 2번 풍선이 작은 경우)이므로 낮은 풍선 터트리는 기회를 사용하지 않고 2 반환

- n이 3이면, 가운데 풍선을 기준으로 4가지 경우의 수로 나눈다.

  ㄴ 가운데 풍선 기준, 왼쪽은 작고 오른쪽은 큰 경우

  ㄴ 가운데 풍선 기준, 왼쪽은 크고 오른쪽은 작은 경우

  ㄴ 가운데 풍선 기준, 왼쪽은 작고 오른쪽도 작은 경우

  ㄴ 가운데 풍선 기준, 왼쪽은 크고 오른쪽도 큰 경우

 

그러면 맨 왼쪽 풍선과 맨 오른쪽 풍선은 무조건 남을 수 있는 풍선이라는 걸 알 수 있다.

 

이를 통해 맨 왼쪽 풍선과 맨 오른쪽 풍선을 제외하고 반복문을 순회하면서

비교하려고 하는 풍선의 왼쪽 그룹의 최솟값과 오른쪽 그룹의 최솟값을 비교해

둘 다 작다면 해당 풍선은 건너뛰고 다음 풍선을 확인한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int[] a) {
        int size = a.length;
        if(size == 1)   return 1;    // 풍선 개수가 1개면 1개만 남길 수 있음
        
        int[] leftMin = new int[size];  // 각 인덱스에서 왼쪽  원소의 최소값 저장
        int[] rightMin = new int[size]; // 각 인덱스에서 오른쪽 원소의 최대값 저장
        int l = a[0];   // 왼쪽 값 중 최소값
        int r = a[size -1]; // 오른쪽 값 중 최소값
        
        // i일 때 왼쪽 원소의 최소값 저장
        for(int i = 1 ; i < size -1 ; i++) {
            if(l > a[i]) // 왼쪽 끝+1의 요소가 left보다 작으면 남길 수 있음
                l = a[i];
            leftMin[i] = l;
        }
        
        // i일 때 오른쪽 원소의 최소값 저장
        for(int i = size -2 ; i > 0 ; i--) {
            if(r > a[i]) // 오른쪽 끝-1의 요소가 right보다 작으면 남길 수 있음
                r = a[i];
            rightMin[i] = r;
        }       
        
        int answer = 2; // 최후까지 남기는 게 가능한 풍선들 개수 (풍선이 2개 이상이면 2개부터 시작)
        for(int i = 1 ; i <= size -2 ; i++) {
            if(a[i] > leftMin[i] && a[i] > rightMin[i]) continue; // 양쪽의 최솟값보다 크다면 continue
            answer++;
        }
        
        return answer;
    }
}

 

 

 

➕ 다른 풀이 방식

HashSet을 활용한 풀이 !!!🙊🙊

import java.util.*;

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

 

---

💦 어려웠던 점

- 규칙을 못 찾겠으면 역시 직접 그려보고 규칙을 찾는 수밖에 없는 것 같다,,

 

 

🧐 새로 알게 된 내용

- 다아아아아아...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스]풍선 터트리기 - JAVA

[Programmers] 풍선 터트리기 (Java)

[프로그래머스] 풍선 터트리기 Java 풀이

[프로그래머스 level_3 / 월간 코드 챌린지 시즌 1] 풍선 터트리기 for JAVA

 

 

 

친절한 설명..

[java] 프로그래머스 (풍선 터트리기) Level 3