(javascript) 프로그래머스 풍선 터트리기

프로그래머스 알고리즘 문제풀이 풍선 터트리기

[문제 링크]

https://programmers.co.kr/learn/courses/30/lessons/68646?language=javascript

[문제]

문제 설명

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

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

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

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

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

[풀이]

알고리즘 문제풀이가 오랜만이라 문제를 읽었을 때, 어떠한 유형의 문제인지 풀이방식을 떠올리는 것이 쉽지 않았습니다. 그래서 알고리즘의 대표유형 (다이나믹, bfs/dfs, 그리디, 분할, ... )등의 문제풀이 방식을 다시 공부하고 와서 문제풀이를 진행하였습니다. 여담이지만, 이전에 풀어본 문제들을 다시 기억하는게 쉽지않아 블로그에 문제풀이를 정리하고 유형을 나누어 놓는것이 좋을 것같다고 생각되어 글을 적습니다.

문제유형은 불필요한 계산을 줄이고, 효율적으로 최적의 해를 찾는 문제유형인 다이나믹 프로그래밍에 가깝다고 생각 들었습니다.

• 첫번째 문제풀이
  문제 풀이 방식은 완전탐색에 가깝게 진행하였습니다.

1. 번호가 작은 풍선을 한번만 터트리는 행위인 찬스를 이용한다면 좌우 끝단에 존재하는 풍선은 무조건 살아남을 수 있을 것입니다.

2. 3개의 풍선이 남아있을때, 가운데에 존재하는 풍선은 좌우보다 하나라도 작다면 찬스를 이용하여 살아남을 수 있을 것입니다.
   예를 들어) 1 2 3 (O) 2 1 3 (O) 1 3 2 (x)

3. 따라서 중간지점에 존재하는 풍선을 남기기 위해서는
   $min(a_1,a_2,...,a_{n-1})$ , $a_n$ , $min(a_{n+1},a_{n+2},...,a_{m})$ 의 값중 $a_n$값 이 좌우에 놓인 $min(...)$ 값 중에 더 작은 값이 존재하여야 합니다.

   이런식으로 문제풀이를 진행하고 수식을 입력하게 된다면 $a_n$값을 확인할 때마다, 좌우에 놓인 값들중 최소값을 구해야 하기때문에 시간복잡도가 $O(n^2)$이 된다.

• 두번째 문제풀이
  시간초과로 문제를 풀지 못하였기 때문에, 시간복잡도를 줄이는데에 중점을 두어 생각하였습니다.

1. $O(n^2)$의 시간복잡도를 $O(n)$으로 바꾸기 위해 매번 좌우의 최솟값을 구하는 공식을 단순하게 바꾸었습니다.
2. 기존의 좌우에 있던 $min(...)$을 $l,r$이라는 변수에 각각 담아 $n$값이 증가할 때마다, $l$과 $r$값을 변경하였습니다.
3. 이렇게 진행하게 되면 3 1 2 와 같은경우 1을 증가하는 함수가 한번, 뒤에서오는 함수가 한번 씩 체크하여 answer값이 2번 증가합니다.
4. 따라서 모든 값을 $arr.push()$하고 마지막에 중복된 값을 제거하였습니다.

[성공 코드]

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
}

[셀프 피드백]

문제의 유형을 찾아 풀이법을 생각하기까지 오래걸렷습니다. -> 유형별 풀이법 정리가 필요
이번 문제는 유형을 알고도 모든 min값을 구하는 것에서 벗어나지 못하여 두번째 풀이로 가는 시간이 오래걸렸습니다. -> 경험부족