🎈 풍선 터트리기
첫 번째는 DFS로 접근하여 풀어서 시간 초과가,두 번째는 BFS로 접근하여 풀어서 메모리 초과가 났다. 결국 다른 사람의 풀이를 참고하였고, 수학적으로 접근해(?) 해결할 수 있었다.
문제 설명
일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.
- 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
- 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.
여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.
당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.
일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- a의 길이는 1 이상 1,000,000 이하입니다.
- a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
- a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
- a의 모든 수는 서로 다릅니다.
입출력 예
| a | result |
| [9,-1,-5] | 3 |
| [-16,27,65,-2,58,-92,-71,-68,-61,-33] | 6 |
💡 나의 풀이
❌ 첫 번째 풀이: 시간 초과
class Solution {
static int[] balloon;
static boolean[] survived;
public int solution(int[] a) {
boolean[] popped = new boolean[a.length];
survived = new boolean[a.length];
balloon = a;
dfs(1, 1, popped);
int cnt = 0;
for(boolean surv: survived)
if(surv) cnt++;
return cnt;
}
private void dfs(int depth, int chance, boolean[] popped) {
if(depth == popped.length) {
for(int i=0; i<popped.length; i++) {
if(!popped[i]) {
survived[i] = true;
return;
}
}
}
for(int i=0; i<popped.length; i++) {
if(popped[i]) continue;
int lIdx = leftIdx(i, popped);
int rIdx = rightIdx(i, popped);
//찬스를 이미 사용한 경우
if(chance == 0) {
if(mustUseChance(i, lIdx, rIdx))
continue;
popped[i] = true;
dfs(depth+1, 0, popped);
}
//찬스를 사용할 수 있는 경우
else {
popped[i] = true;
if(mustUseChance(i, lIdx, rIdx))
dfs(depth+1, 0, popped);
else if(canNotUseChance(i, lIdx, rIdx))
dfs(depth+1, 1, popped);
else {
dfs(depth+1, 0, popped);
dfs(depth+1, 1, popped);
}
}
popped[i] = false;
}
}
//찬스를 반드시 사용해야 하는 경우 true를 리턴
private boolean mustUseChance(int idx, int lIdx, int rIdx) {
if(lIdx == -1 && balloon[idx] < balloon[rIdx])
return true;
if(rIdx == balloon.length && balloon[idx] < balloon[lIdx])
return true;
if(lIdx != -1 && rIdx != balloon.length &&
balloon[idx] < balloon[lIdx] && balloon[idx] < balloon[rIdx])
return true;
return false;
}
//찬스를 사용할 수 없는 경우 true를 리턴
private boolean canNotUseChance(int idx, int lIdx, int rIdx) {
if(lIdx == -1 && balloon[idx] > balloon[rIdx])
return true;
if(rIdx == balloon.length && balloon[idx] > balloon[lIdx])
return true;
if(lIdx != -1 && rIdx != balloon.length &&
balloon[idx] > balloon[lIdx] && balloon[idx] > balloon[rIdx])
return true;
return false;
}
//idx 왼쪽의 터지지 않은 풍선 중 가장 가까운 것의 index를 리턴
private int leftIdx(int idx, boolean[] popped) {
int left = idx-1;
while(left >= 0) {
if(!popped[left])
break;
left--;
}
return left;
}
//idx 오른쪽의 터지지 않은 풍선 중 가장 가까운 것의 index를 리턴
private int rightIdx(int idx, boolean[] popped) {
int right = idx+1;
while(right < popped.length) {
if(!popped[right])
break;
right++;
}
return right;
}
}DFS를 이용하여 풀이하였다.
풍선을 터뜨릴 수 있는 모든 경우의 수를 탐색하여, 마지막에 남는 풍선을 체크한다.
for문 내에서 터지지 않은 풍선에 대해 dfs를 재귀호출 할 때,
다음과 같은 로직에 따라 처리하게 된다.
번호가 더 작은 풍선을 터뜨리는 행위를 "찬스"라고 한다면,
찬스를 사용한 경우와 사용하지 않은 경우로 나눠볼 수 있다.
- 찬스를 이미 사용한 경우
- 현재 풍선이 양쪽보다 번호가 작아서 찬스를 무조건 사용해야 한다면, 터뜨릴 수 없으므로 다음 풍선을 검사한다.
- 그렇지 않다면, 현재 풍선을 터뜨리고 dfs를 재귀호출 한다.
- 찬스를 아직 사용하지 않은 경우
- 현재 풍선이 양쪽보다 번호가 작아서 찬스를 무조건 사용해야 한다면, 풍선을 터뜨리고 찬스를 0으로 set하여 dfs를 재귀호출 한다.
- 현재 풍선이 양쪽보다 번호가 커서 찬스를 사용할 수 없다면, 풍선을 터뜨리고 찬스를 그대로 1로 set하여 dfs를 재귀호출 한다.
- 위 두 경우에 모두 해당하지 않아 찬스를 써도 되고 안 써도 되는 상황이라면, 두 상황 모두를 고려하여 dfs를 재귀호출 한다.
⌛ 시간복잡도
이 경우 (depth == n)이 되기 전 까지 dfs가 재귀호출되고,
각 dfs 호출마다 for loop을 n회 돌기 때문에
O(nn)이라는 쓰레기 시간복잡도를 가진다.
(문제에서 n의 최댓값 == 1,000,000 ..🤯)
❌ 두 번째 풀이: 메모리 부족
import java.util.*;
class Node {
int idx;
int chance;
int popNum;
boolean[] popped;
Node(int idx, int chance, int popNum, boolean[] popped) {
this.idx = idx;
this.popNum = popNum;
this.chance = chance;
this.popped = popped;
}
}
class Solution {
static int[] ball;
static Queue<Node> queue;
static boolean[] visited;
static Set<Integer> survived;
public int solution(int[] a) {
ball = a;
survived = new HashSet<>();
bfs();
return survived.size();
}
private void bfs() {
for(int i=0; i<ball.length; i++) {
System.out.println();
queue = new LinkedList<>();
visited = new boolean[ball.length];
offerQueue(i, 1, 0, visited);
while(!queue.isEmpty()) {
Node now = queue.poll();
int chance = now.chance;
int popNum = now.popNum;
boolean[] popped = now.popped;
if(popNum == ball.length-1) {
for(int j=0; j<popped.length; j++) {
if(!popped[j]) {
survived.add(ball[j]);
break;
}
}
continue;
}
for(int j=0; j<ball.length; j++) {
if(popped[j]) continue;
offerQueue(j, chance, popNum, popped);
}
}
}
}
private void offerQueue(int idx, int chance, int popNum, boolean[] popped) {
int lIdx = leftIdx(idx, popped);
int rIdx = rightIdx(idx, popped);
boolean[] poppedCpy = new boolean[popped.length];
for(int i=0; i<popped.length; i++)
poppedCpy[i] = popped[i];
poppedCpy[idx] = true;
if(mustUseChance(idx, lIdx, rIdx)) {
if(chance == 0) return;
queue.offer(new Node(idx, 0, popNum+1, poppedCpy));
}
else if(canNotUseChance(idx, lIdx, rIdx))
queue.offer(new Node(idx, chance, popNum+1, poppedCpy));
else {
queue.offer(new Node(idx, 0, popNum+1, poppedCpy));
if(chance == 1)
queue.offer(new Node(idx, 1, popNum+1, poppedCpy));
}
}
//찬스를 반드시 사용해야 하는 경우 true를 리턴
private boolean mustUseChance(int idx, int lIdx, int rIdx) {
if(lIdx == -1 && ball[idx] < ball[rIdx])
return true;
if(rIdx == ball.length && ball[idx] < ball[lIdx])
return true;
if(lIdx != -1 && rIdx != ball.length &&
ball[idx] < ball[lIdx] && ball[idx] < ball[rIdx])
return true;
return false;
}
//찬스를 사용할 수 없는 경우 true를 리턴
private boolean canNotUseChance(int idx, int lIdx, int rIdx) {
if(lIdx == -1 && ball[idx] > ball[rIdx])
return true;
if(rIdx == ball.length && ball[idx] > ball[lIdx])
return true;
if(lIdx != -1 && rIdx != ball.length &&
ball[idx] > ball[lIdx] && ball[idx] > ball[rIdx])
return true;
return false;
}
//idx 왼쪽의 터지지 않은 풍선 중 가장 가까운 것의 index를 리턴
private int leftIdx(int idx, boolean[] popped) {
int left = idx-1;
while(left >= 0) {
if(!popped[left])
break;
left--;
}
return left;
}
//idx 오른쪽의 터지지 않은 풍선 중 가장 가까운 것의 index를 리턴
private int rightIdx(int idx, boolean[] popped) {
int right = idx+1;
while(right < popped.length) {
if(!popped[right])
break;
right++;
}
return right;
}
}BFS를 이용하여 풀이하였다.
Node 타입의 인스턴스를 저장하는 Queue가 존재하며,
각각의 Node 인스턴스는 지금까지 터진 풍선에 대한 정보를 필드로 가진다.
(보통의 BFS에서의 visited 배열이 각각의 Node에 필드로 들어가 있다고 생각할 수 있다.)
bfs 메서드는 다음과 같은 로직을 따른다.
- Queue에서 node를 하나 뽑는다.
- if (node.popNum == 풍선개수-1) : 터지지 않은 풍선을 survived에 추가하고, 다시 1을 수행한다.
- else : node에 저장된 popped 배열을 이용해, 터지지 않은 풍선에 대해 offerQueue 메서드를 호출한다.
- offerQueue 메서드는 1차 시도(DFS)에서와 같은 방법으로 찬스를 사용한 경우와 사용하지 않은 경우로 나눠 queue에 new Node를 추가한다.
💾 공간복잡도
이 경우 Queue에 n!개의 node가 저장되고,
각 node마다 길이 n의 배열을 필드로 가지기 때문에
역시 O(n*n!)라는 쓰레기 공간복잡도를 가진다.
(a의 길이가 1,000,000일 경우 4B * 1,000,000 * 1,000,000! 의 fixed memory 공간 필요 ..🤯)
⭕ 세 번째 풀이
import java.util.*;
class Solution {
public int solution(int[] a) {
Set<Integer> set = new HashSet<>();
int minL = a[0];
int minR = a[a.length-1];
for(int i=1; i<a.length; i++) {
set.add(minL);
minL = Math.min(minL, a[i]);
}
for(int i=a.length-1; i>=0; i--) {
set.add(minR);
minR = Math.min(minR, a[i]);
}
return set.size();
}
}결국 다른 사람들의 풀이를 참고하였다.
나는 풍선을 일일이 터뜨려보며 해를 구하는 브루트 포스 방법으로만 접근하고 있었는데,
이 문제를 구현하기 전에 약간 머리만 굴려보면 최소화된 시간복잡도로 보다 간단히 해결할 수 있었다. 😢
- 양쪽 끝에 있는 2개의 풍선을 EP(EndPoint)라 하자.
- EP 사이에 있는 풍선들을 큰 값부터 차례로 모두 터뜨리고 2개의 EP만 남았다고 가정하자.
- 이 때, 두 EP는 모두 마지막까지 살아남을 수 있다. (찬스를 사용하지 않았으므로)
👉 즉, EndPoint가 될 수 있다면, 마지막까지 살아남을 수 있다.
또한, EP가 아닌 풍선이 EP가 될 수 있는 경우는 다음과 같다.
👉 EP에 인접한 풍선이 해당 EP보다 번호가 작다면, EP 풍선을 터뜨리고 자신이 EP가 될 수 있다.
정리하면, 다음과 같은 로직에 따라 마지막까지 살아남을 수 있는 풍선들을 추려낼 수 있다.
"EP에 인접한 풍선 B가 EP보다 작다면, B를 survived 처리하고 EP를 B로 갱신한다."
위의 설명으로도 코드가 이해되지 않는다면, 다음 예시를 참고해보자.
"survived"라는 이름의 HashSet에 살아남을 수 있는 풍선의 번호를 저장하며 진행한다.
우선, 양쪽 끝 풍선인 16, -68을 저장하고 시작하자.
[16, -2, 58, -92, -71, -68] //survived : [16, -68]
우선 왼쪽 EP부터 검사한다.
위의 배열에서 -2는 맨 왼쪽 끝의 16보다 작으므로, 왼쪽 끝 숫자가 될 수 있다.
👉 16을 터뜨리고, -2를 왼쪽 끝 숫자로 만든다.
👉 survived set에 -2를 추가한다.
[-2, 58, -92, -71, -68] //survived : [16, -68, -2]
위의 배열에서 58은 맨 왼쪽 끝의 -2보다 크므로, 왼쪽 끝 숫자가 될 수 없다.
👉 반복문을 빠져나온다.
[-2, 58, -92, -71, -68] //survived : [16, -68, -2]
이제 오른쪽 EP를 검사하자.
위의 배열에서 -71은 맨 오른쪽 끝의 -68보다 작으므로, 오른쪽 끝 숫자가 될 수 있다.
👉 -68을 터뜨리고, -71을 오른쪽 끝 숫자로 만든다.
👉 survived set에 -71을 추가한다.
[-2, 58, -92, -71] //survived : [16, -68, -2, -71]
위의 배열에서 -92는 맨 오른쪽 끝의 -71보다 작으므로, 오른쪽 끝 숫자가 될 수 있다.
👉 -71을 터뜨리고, -92를 오른쪽 끝 숫자로 만든다.
👉 survived set에 -92를 추가한다.
[-2, 58, -92] //survived : [16, -68, -2, -71]
위의 배열에서 58은 맨 오른쪽 끝의 -92보다 크므로, 오른쪽 끝 숫자가 될 수 없다.
👉 반복문을 빠져나온다.
위의 예시의 경우 최종 survived set은 [16, -68, -2, -71]로, 4개의 풍선이 살아남을 수 있게 된다.
코딩테스트 연습 - 풍선 터트리기
[-16,27,65,-2,58,-92,-71,-68,-61,-33] 6
programmers.co.kr
'Algorithm Test > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 단속카메라 (JAVA) (0) | 2021.04.30 |
|---|---|
| [프로그래머스] 정수 삼각형 (JAVA) (0) | 2021.04.30 |
| [프로그래머스] [2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠 (JAVA) (0) | 2021.04.29 |
| [프로그래머스] 섬 연결하기 (JAVA) (0) | 2021.04.29 |
| [프로그래머스] 단어 변환 (JAVA) (0) | 2021.04.01 |