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

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

2. 입력

• a의 길이는 1 이상 1,000,000 이하입니다.
  • a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
  • a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
  • a의 모든 수는 서로 다릅니다.

3. 예제

a	result
[9,-1,-5]	3
[-16,27,65,-2,58,-92,-71,-68,-61,-33]	6

4. 풀이

이번 문제는 풍선을 최종적으로 남아 있을 수 있는지 여부를 2번째 풍선부터 확인하여 개수를 Count 하는 문제입니다.

 

여러 풍선이 일렬로 있을 때 어떤 풍선이 남을 수 있고 어떤 풍선이 남을 수 없는지 확인이 필요합니다.

 

풍선이 총 1개인 경우는 무조건 풍선이 남아 있을 수 있으므로 1을 반환합니다.

 

풍선이 총 2개인 경우는 2가지의 경우로 풍선이 있을 것입니다.

1. 1번 풍선이 작고 2번 풍선이 큰 경우
2. 1번 풍선이 크고 2번 풍선이 작은 경우

위 2가지 경우로 풍선이 나열될 수 있습니다. 

 

이 경우 1번과 2번 풍선 모두 남아 있을 수 있으므로 2를 반환하면 됩니다.

 

그럼 풍선이 총 3개인 경우는 4가지의 경우로 풍선이 있을 수 있습니다.

1. 가운데 풍선을 기준으로 왼쪽은 작고 오른쪽이 큰 경우(오름차순)
   

   

   오름차순의 경우 모든 풍선이 남아 있을 수 있습니다.
   
   
2. 가운데 풍선을 기준으로 왼쪽이 크고 오른쪽이 작은 경우(내림차순)
   

   

   내림차순의 경우 모든 풍선이 남아 있을 수 있습니다.
   
   
3. 가운데 풍선을 기준으로 왼쪽, 오른쪽 모두 작은 경우
   

   

   양쪽이 모두 작은 경우는 가운데 수를 최종적으로 남길 수 없습니다.
   
   첫 제거에서 작은 값을 제거한 경우 두 번째 제거에서는 무조건 가운데 풍선을 제거해야 되며 반대로 첫 제거에서 큰 값인 가운데 풍선을 제거한다면 당연히 가운데 풍선을 남기지 못하기 때문입니다.
   
   

   

   첫 제거에서 왼쪽의 작은 값을 제거한 경우 오른쪽과의 제거에서는 무조건 2를 제거해야 됩니다.
   
   

   

   첫 제거에서 오른쪽의 작은 값을 제거한 경우 또한 왼쪽의 제거에서 무조건 2를 제거해야 됩니다.
   
   
4. 가운데 풍선을 기준으로 왼쪽, 오른쪽 모두 큰 경우
   

   

   양쪽이 모든 큰 경우 모든 풍선이 남아 있을 수 있습니다.

위 4가지 경우로 풍선이 나열될 수 있습니다.

 

총 풍선 1~3개까지 경우를 살펴보면 왼쪽 맨 처음 풍선과 오른쪽 맨 처음 풍선은 무조건 남을 수 있는 풍선이라는 것을 알 수 있습니다.

 

또한 문제 풀이의 핵심인 왼쪽 풍선 그룹들의 최솟값과 오른쪽 풍선 그룹들의 최솟값이 현재 풍선의 값보다 작다면 해당 풍선은 최종적으로 남을 수 없는 풍선이라는 것을 알 수 있습니다.

 

그럼 첫 풍선과 마지막 풍선을 제외하고 반복문을 순회하면서 비교하고자 하는 풍선의 왼쪽 그룹의 최솟값과 오른쪽 그룹의 최솟값을 비교하여 둘 다 작다면 해당 풍선은 건너뛰고 다음 풍선을 확인합니다.

 

만약 왼쪽, 오른쪽 둘 중 하나만 작거나 모두 큰 경우라면 남아있을 수 있는 풍선이므로 카운트를 증가시켜 문제를 풀 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

if (a.length == 1)
	return 1;

int leftMin = a[0];
int[] rightMin = new int[a.length];
rightMin[a.length - 1] = a[a.length - 1];

for (int i = a.length - 2; i > 0; i--)
	rightMin[i] = Math.min(rightMin[i + 1], a[i]);

int answer = 2;
for (int i = 1; i < a.length - 1; i++) {
	if (!(leftMin < a[i] && rightMin[i] < a[i]))
		answer++;

	leftMin = Math.min(leftMin, a[i]);
}

return answer;