[programmers] Lv3. 풍선터트리기 Javascript | protect-me
🕊 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()을 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 - 최초 작성
Lv3. 풍선터트리기 Javascript
https://programmers.co.kr/learn/courses/30/lessons/68646
// 최종 코드
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()을 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 - 최초 작성
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;
}
구현하기 전, 먼저 시간복잡도를 계산해보는 것이 중요.
O()을 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
Author And Source
이 문제에 관하여([programmers] Lv3. 풍선터트리기 Javascript | protect-me), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@protect-me/programmers-Lv3.-풍선터트리기-Javascript-e7fwxhtl저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)