문제 출처
나의 풀이
jump을 계산해서 매번 찾으려했으나 너무 비효율적이었고 정확하지도 않았다.
1차시도(실패)
function solution(stones, k){
let answer = 0
let jump = 0
while(1){
for(let i=0; i<stones.length; i++){
if(jump >= k) break
const curr = stones[i]
if(curr > 0){
stones[i] -= 1
jump = 0
}
else if(curr === 0) jump += 1
}
if(jump >= k) break
else answer++
}
return answer
}2차시도 (정확성 성공, 효율성 실패)
0인 돌다리가 k개 있으면 더 이상 돌다리를 건널 수 없다.
이때 생각을 바꿔서 매번 점프 거리를 구하는 게 아니라 각 돌다리를 index마다 k개만큼 잘라서 0이 될때까지 빼주면 그게 각 돌다리에서의 최대값이 되므로 이렇게 for문을 1번만 반복하면 된다.
그리고 k개가 모두 0이 된다는 건, 결국 k개에서 가장 큰 값만큼이 최대값이 된다는 의미이고, 그 최대값들 중에서 최소값이 문제에서 요구하는 답이 된다.
하지만 여전히 시간초과가 발생한다. slice 혹은 sort 때문일까?
아래처럼 연산을 바꾸더라도 약간은 줄였지만, 시간초과는 여전하다
const max = Math.max(...stones.slice(i, i+k))
answer = Math.min(answer, max)function solution(stones, k) {
let answer = Number.MAX_SAFE_INTEGER
for(let i=0; i<=stones.length-k; i++){
const arr = [...stones.slice(i, i+k)].sort((a,b) => b - a)
answer = Math.min(answer, arr[0])
}
return answer
}
console.log(solution([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))다른 풀이 1
입력값의 크기를 생각하는 게 중요하다.
돌의 개수가 최대 20만으로 주어졌고, 각 돌의 값은 최대 2억이므로 가능한 답은 2억이 될수 있다. 모든 돌이 2억이면 2억명이 돌다리를 건널 수 있기 때문이다. 앞으로는 이렇게 최대 크기가 억 단위를 넘어가면 O(n) 보다 더 빠른 O(logn)을 떠올리면 좋을 것 같다.
O(logn)을 달성하기에 좋은 접근은 역시 이분탐색이다.
left와 right를 잡아놓고 left가 right보다 커질 때까지, while문을 반복한다.
mid를 잡고 copy 배열에서 각 원소를 mid 만큼 뺀다. 그래서 0보다 작은 값이 k개 이상 발견되면 그 경우는 건널 수 없는 경우가 된다. 건널 수 없는 경우 큰 값은 right를 당겨주고, 반대로 건널 수 있는 경우는 left 값을 우측으로 당겨서 범위를 좁혀나간다.
이렇게 범위를 좁혀 나가다 보면 건널 수 있는 최대인원을 찾을 수 있다.
function solution (stones, k) {
let left = 1;
let right = 200000000;
while(left <= right) {
const mid = (left + right) / 2 >> 0;
const copy = stones.slice();
let flag = false;
let count = 0;
for(let i = 0; i < copy.length; i++) copy[i] -= mid;
for(const value of copy) {
count = value <= 0 ? count+1 : 0;
if(count === k) {
flag = true;
break;
}
}
flag ? right = mid - 1 : left = mid + 1;
}
return left;
}오른쪽 시프트 연산자(>>)는 모든 비트를 전부 오른쪽으로 이동시키는 것과 같다. 즉, 2로 나누는 것과 같다. 이떄 >> 0이면 내림처리를 하는 것과 같다(Math.floor()).
연속된 값을 찾을 때는
count = value <= 0 ? count+1 : 0와 같이 구현하면 좋다. 0을 연속적으로 만나면 값이 계속 증가하지만 0보다 큰 값을 만나면 다시 count 값이 초기화된다.
다른 풀이 2
마찬가지로 이분탐색
function checkStone(stones, mid, k) {
let now = 0
for(let i = 0; i < stones.length; i++) {
if(stones[i] < mid) now += 1
else now = 0
if(now >= k) return false
}
return true
}
function solution(stones, k) {
let left = 1
let right = 200000000
while(left < right-1) {
let mid = parseInt((left + right) / 2)
if (checkStone(stones, mid, k)) left = mid
else right = mid
}
return left
}다른 풀이 3
function solution(stones, k) {
stones.push(Infinity);
let stack = [{count: Infinity, idx: -1}];
let answer = Infinity;
for (let i = 0; i < stones.length; i++) {
const right = { count: stones[i], idx: i };
while (stack[stack.length - 1].count < right.count) {
const mid = stack.pop();
const left = stack[stack.length - 1];
if (right.idx - left.idx > k) {
answer = Math.min(answer, mid.count);
}
}
stack.push(right);
}
return answer;
}또는
function solution(stones, k) {
stones.push(Infinity);
let stack = [-1];
let minOfMax = Infinity;
for (let index = 0; index < stones.length; index++) {
const value = stones[index];
while (stones[stack[stack.length - 1]] < value) {
const item = stack.pop();
if (stack[stack.length - 1] >= index - k) continue;
minOfMax = (stones[item] < minOfMax)? stones[item] : minOfMax;
}
stack.push(index);
}
return minOfMax;
}참고
