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

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-04-27

  • 해결 방법 :

    • 한 풍선을 기준으로 각 좌측과 우측의 최솟값 둘 다 그 풍선보다 작다면 터트릴 수 없다.
    • 따라서 좌측과 우측의 최솟값을 각각 선언하고
      • 좌측의 최솟값 < 우측의 최솟값인 경우
        • r 포인터를 1 감소시킨 뒤
        • 우측의 최솟값과 비교하여 더 작다면
          • 우측 최솟값 업데이트 및 answer += 1
      • 좌측의 최솟값 > 우측의 최솟값인 경우
        • l 포인터를 1 증가시킨 뒤
        • 좌측의 최솟값과 비교하여 더 작다면
          • 좌측 최솟값 업데이트 및 answer += 1
    • 즉, 우측의 최솟값과 좌측의 최솟값 중 큰 값의 한 칸 옆 풍선과 비교하여 업데이트

  • 회고 :

    • 한 풍선을 기준으로 각 좌측과 우측의 최솟값 둘 다 작으면 안된다는 조건을 떠올리는건 쉬웠으나, 포인터를 두 개 두고 접근하는 방법을 생각하는게 어려웠다.

  • 코드

    function solution(a) {
  let answer = 1;

  let l = 0,
    r = a.length - 1;
  let leftMin = a[l],
    rightMin = a[r];

  while (l < r) {
    if (leftMin < rightMin) {
      r -= 1;

      if (rightMin > a[r]) {
        rightMin = a[r];
        answer += 1;
      }
    } else {
      l += 1;

      if (leftMin > a[l]) {
        leftMin = a[l];
        answer += 1;
      }
    }
  }

  return answer;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges