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

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

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

https://programmers.co.kr/learn/courses/30/lessons/68646

풀이 : 이 문제는 접근방식이 필요하는 문제인 것 같다

• [left, right] 방식로 2개의 풍선의 기준으로 보았을 때, 제일 왼쪽의 풍선은 마지막까지 남길 수 있다. 마찬가지로 제일 오른쪽의 풍선도 마지막까지 남길 수 있다.
• 가운데 풍선의 경우, left와 right 중 하나가 되기 위해서는 left, right보다 숫자가 작아야 한다. <숫자가 작아야 마지막까지 남는다.>

풀이 1. (중급) - HashSet을 통해 left, right보다 작은 숫자를 걸러낸다.

import java.util.*;
class Solution {
    public int solution(int[] a) {
        HashSet <Integer> set = new HashSet<Integer>();
		int min = a[0];
		for (int i = 1; i < a.length; i++) {
			set.add(min);
			min = Math.min(a[i], min);
		}
		min = a[a.length-1];
		for (int i = a.length-2; i >= 0; i--) {
			set.add(min);
			min = Math.min(a[i], min);
		}
        return set.size();
    }
}

풀이 2. (중급) - 배열을 통해 숫자를 걸러낸다.

class Solution {
    public int solution(int[] a) {
		int answer = 2;
		int [][] map = new int [a.length][2];
		int l = a[0], r = a[a.length-1];
		for (int i = 1; i < a.length-1; i++) {
			if(l > a[i]) l = a[i];
			map[i][0] = l;
		}
		for (int i = a.length-2; i > 0; i--) {
			if(r > a[i]) r = a[i];
			map[i][1] = r;
		}
		for (int i = 1; i < a.length-1; i++) {
			if(a[i] <= map[i][0] || a[i] <= map[i][1]) answer++;
		}
        return answer;
    }
}

풀이 2. (고급) - 한 번에 걸러낸다.

import java.util.*;
class Solution {
    public int solution(int[] a) {
       int answer = 2; // 처음과 끝은 무조건 남길 수 있다.
       int l = a[0], r = a[a.length-1];
       for (int i = 1; i < a.length-1; i++) { // 가운데 풍선을 걸러낸다.
		if(l > a[i]) {
			l = a[i]; 
			answer++;
		}
		if(r > a[a.length-1-i]) {
			r = a[a.length-1-i];
			answer++;
		}
	}
        return l ==r ? answer-1 : answer; // l과 r이 같으면 중복 발생
    }
}