🕊 Link

Lv3. 풍선터트리기 Javascript
https://programmers.co.kr/learn/courses/30/lessons/68646

🧑🏻‍💻 Code(javascript)

// 최종 코드
function solution(a) {
  if (a.length <= 3) return a.length;

  let leftArr = [];
  let rightArr = [];
  let leftMin = a[0];
  let rightMin = a[a.length - 1];
  a.forEach((_, i) => {
    if (a[i] < leftMin) {
      leftMin = a[i];
    }
    leftArr.push(leftMin);

    if (a[a.length - 1 - i] < rightMin) {
      rightMin = a[a.length - 1 - i];
    }
    rightArr.push(rightMin);
  });

  rightArr.reverse();

  let count = 0;
  a.forEach((el, i) => {
    if (el === leftArr[i] || el === rightArr[i]) count++;
  });
  return count;
}

💡 Solution

• 3보다 작거나 같으면 모든 수가 마지막까지 남을 수 있음.
• 왼쪽에 보다 작은 수 있으면, 오른쪽에는 보다 큰 수만 있어야함.
• 왼쪽에 보다 작은 수가 없으면, 오른쪽에는 보다 작은 수가 있어도 됨.
• 즉 왼쪽, 오른쪽에 해당 수보다 작은 수가 없거나, 한쪽에만 있어야함.
• 위와 같은 조건으로 구현하였으나, 테스트 11~15 시간 초과.

• 각 자리의 좌/우 최소값을 구해서 배열에 넣어두고 비교하는 것으로 작전 변경.

function solution(a) {
  // 3보다 작거나 같으면 모든 수가 마지막까지 남을 수 있음.
  if (a.length <= 3) return a.length;

  let leftArr = [];
  let rightArr = [];
  let leftMin = a[0];
  let rightMin = a[a.length - 1];
  a.forEach((_, i) => {
    // i를 증가시키면서 left의 최소값을 체크
    if (a[i] < leftMin) {
      leftMin = a[i];
    }
    leftArr.push(leftMin);
	
    // i를 증가시키면서 뒤에서부터 역순으로 right의 최소값을 체크
    if (a[a.length - 1 - i] < rightMin) {
      rightMin = a[a.length - 1 - i];
    }
    rightArr.push(rightMin);
  });

  // rightArr는 뒤에서 부터 돌았기 때문에 reverse 필요
  rightArr.reverse();

  let count = 0;
  // 최소값Arr[i]와 현재 값(el)이 같으면 현재 값이 최소값이라는 의미
  // 양쪽 모두에서 현재 값(el)이 최소값이거나 한쪽만이라도 최소값이면 조건에 만족.
  a.forEach((el, i) => {
    if (el === leftArr[i] || el === rightArr[i]) count++;
  });
  return count;
}

👨🏻‍💻💭 Self Feedback

구현하기 전, 먼저 시간복잡도를 계산해보는 것이 중요.
O($n2$)을 O(n)으로 내리는 법을 강구하는 것이 쉽지는 않았다.

• 1차 시도 코드 : 시간 초과

function solution(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    let leftFlag = 0;
    let rightFlag = 0;
    for (let left = 0; left < i; left++) {
      if (arr[left] < arr[i]) {
        leftFlag++;
        break;
      }
    }
    for (let right = i + 1; right < arr.length; right++) {
      if (arr[right] < arr[i]) {
        rightFlag++;
        break;
      }
    }
    if (leftFlag + rightFlag <= 1) {
      count++;
    }
  }
  return count;
}

• 2021.04.14 - 최초 작성

댓글 환영 질문 환영
by.protect-me