문제 : 풍선 터트리기
기본적인 내용
핵심은 끝까지 남기려는 풍선을 기준으로 좌,우 구간의 최소값을 구했을때(leftMin, rightMin),
터트리려는 풍선의 값은 두 최소값 보다 크지 않아야합니다.
한번은 작은 풍선을 터트릴 수 있기 때문에 터트리려는 풍선이
좌,우 최소값중 하나 보다는 클 수 있어도, 둘 보다 커버리면 남길 수 없습니다.
Only one max = 큰 수는 하나 까지만 허용
좌에서 우로 최소값을 갱신하며 배열에 넣고, 우에서 좌로 동일하게 해주고
마지막에 두 최소값 보다 크지않나 보면서 확인해줍니다. 그래서 O(3n)의 방법으로 푸는 방법입니다.
나아가서 두 최소값 중 큰것보다 작기만 하면 되기 때문에 O(n)까지 줄일 수 있습니다.
처음 생각한 방법
배열을 처음부터 반복하면서 값을 기준으로 오른쪽과 왼쪽 배열을 만들어 그들의 최소값과 값을 비교하며 계산을 하였다.
function solution(a) {
var answer = a.length;
for(let i=0;i<a.length;i++)
{
let front =[];
let back = [];
front = a.slice(0,i);
back = a.slice(i+1,a.length);
if(Math.min.apply(null,front) <a[i] && Math.min.apply(null,back) <a[i]){
answer--;
}
}
return answer;
}시간초과 , 런타임 별걸 다 경험했다...
질문 내용에서의 정보
O(n)을 만들기 위해서 오른쪽 끝과 왼쪽 끝에 값부터 시작해
값이 안될 경우는 두 양쪽 값에서 큰값을 기준으로 leftMin이면 오른쪽으로 한칸,rightMin이면 왼쪽으로 한칸갔을 때 해당 값이 leftMin일때 혹은 rightMin일때보다 크다면 불가능한 것으로 찾아낸다.
ex)
5, 10, 8 이 있으면 왼쪽은 5 오른쪽은 8인데 5 < 8 이므로 8에서 왼쪽으로 한칸 갔을때 10은 적어도 오른쪽의 최소값 8보다 크고 왼쪽의 최소값 5보다 크므로 존재할 수 없다.
ex)
10, 18 , 2이 있으면 왼쪽은 10 오른쪽은 2인데 10 < 2 이므로 10에서 오른쪽으로 한칸 갔을때 18은 적어도 오른쪽의 최소값 2보다 크고 왼쪽의 최소값 10보다 크므로 존재할 수 없다.
질문을 토대로 만든 정답 코드
function solution(a) {
let val = 0;
let answer = a.length;
let leftMin = a[0],rightMin = a[a.length-1];
let leftIndex = 0, rightIndex = a.length-1;
while(1){
if(val === a.length-2) //왼쪽 오른쪽 맨끝을 제외한 횟수반복
break;
if(leftMin < rightMin){ //왼쪽min보다 오른쪽min이 클때
if( a[--rightIndex] < rightMin ) //오른쪽에서 찾은 값이 오른쪽 최소값보다 작다면 최소값을 갱신
rightMin = a[rightIndex];
else //오른쪽에서 찾은 값이 오른쪽 최소값보다 크다면 왼쪽 최소값보다도 크므로 최후까지 남길 수 없는 풍선이므로 값을 줄인다.
answer--;
}
else{ //오른쪽min보다 왼쪽min이 크다면
if(leftMin > a[++leftIndex]) //왼쪽에서 찾은 값이 왼쪽 최소값보다 작다면 최소값을 갱신
leftMin = a[leftIndex];
else //왼쪽에서 찾은 값이 왼쪽 최소값보다 크다면 오른쪽 최소값보다도 크므로 최후까지 남길 수 없는 풍선이므로 값을 줄인다.
answer--;
}
val++;
}
return answer;
}느낀점
진짜 이렇게 어떻게 생각하나 싶다.
