[CodeKata] 프로그래머스: 12.28(화), 풍선 터트리기

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

function solution(a) {
  let answers = new Set();
  
  function DFS(arr, canLower) {
    if (arr.length === 1) {
      answers.add(arr[0]);
      return;
    }
    
    for (let i = 0 ; i < arr.length-1 ; i++) {
      let [max, min] = [arr[i], arr[i+1]].sort((a,b) => b-a);
      const newArr = arr.filter(e => e !== max)

      DFS(newArr, canLower)
      if (canLower) DFS(arr.filter(e => e !== min), false)
    }
  }
  
  DFS(a, true)
  
  return answers.size;
}

DFS에 근거한 풀이이다.

인접한 2개의 요소를 비교해가면서 큰 값을 제거해나가고, 이렇게 1개씩 줄어든 배열을 전달하다 1개만 남았을 때 모든 경우를 저장한다.

또한, canLower 이라는 값(boolean)을 전달하여, 이 값이 true인 경우 작은값을 제거한 경우도 추가한다.

 

풀이 자체는 가능하였으나, a.length!(팩토리얼) 의 경우의 수를 고려해야 하는 만큼 시간초과가 발생하였다.

모범답안을 확인하면서, 시간을 더 단축할 수 있는 좋은 방법을 고민해보겠다.

 

🖇 리뷰

function solution(a) {
  var p = []
  var j = []
  var left_min = a[0]
  var right_min = a[a.length - 1]
  
  for (var i = 1; i < a.length - 1; i++) {
    if (left_min > a[i]) {
      left_min = a[i]
      p.push(a[i])

    }
    if (right_min > a[a.length - i - 1]) {
      right_min = a[a.length - i - 1]
      j.push(a[a.length - i - 1])

    }
  }
    
  return [...new Set([...p, ...j])].length + 2
}

• 우선, 양쪽 끝의 풍선은 무조건 살아남을 수 있다. (최소값으로 수렴한 뒤, 끝 풍선보다 크다면 터트리고 / 작다면 작은값 찬스 사용)
• 다음으론, 중간 풍선의 경우들을 고려한다. 양 끝의 최소값들 중, 중간 풍선보다 큰 값이 하나라도 존재하면 해당 풍선은 살아남는다. 
• p, j는 각각 왼쪽, 오른쪽부터 검사해서 살아남는 풍선들을 담는 배열이다. 최소값인 left_min, right_min을 양쪽 끝값으로 초기 설정한다.
• 다음, 중간 풍선들을 탐색하기 위해 i는 1 ~ (a.length - 1) 전까지 순회한다. 양쪽의 현재값 (a[i]. a[a.length - 1 - i]) 들보다 최소값이 크다면 해당 풍선(값)은 살아남을 수 있다. 이를 p, j 에 각각 push하고, 최소값을 현재값으로 갱신해준다.
• 이렇게 모인, p, j 값들이 중복되지 않도록 Set()로 변형해주고, 이 length 값에 2(양끝 풍선)를 더한 최종정답을 반환한다.

 

생각보다, 살아남을 수 있는 풍선의 조건을 확실히 한다면 쉽게 풀 수 있는 문제였다!