두시간 알고리즘 - 3일차, Stack

Stack이 정말 활용도가 높다는 사실을 새삼깨닫고, 오늘은 stack을 심화해서 응용하는 문제들을 풀어보려고 한다. 2시간을 정해두고 알고리즘을 한지 3일이 되었는데, 이제 내일까지만하면 작심삼일은 깨는거다. 

 

1. Maximum Subarray Min-Product: 1h28m53s55

https://leetcode.com/problems/maximum-subarray-min-product/

Maximum Subarray Min-Product - LeetCode

https://www.youtube.com/watch?v=YLesLbNkyjA&t=1166s 

처음엔 하도 이해가 안되서 강사탓을 했지만, 내가 문제였다. 

악필이지만 나름 필기

깨달음이 있었다. Stack을 통해서 현재 체크하는 값을 포함하는 가장큰 subarray 범위의 index를 구할 수 있다. 

monotonous increasing stack을 이용해서, 각 값이 subarray의 최소값일수있도록 인덱스를 stack에 넣는 문제

 

문제자체는 저 해설을 보고 풀었는데, 문제는 JavaScript가 64비트를 지원하지 않고, 53비트까지 지원한다는 거다. 

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt

BigInt - JavaScript | MDN

BigInt를 사용해줘야한다. 

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumMinProduct = function(nums) {
    const modulo = BigInt(Math.pow(10, 9) + 7);
    
    // index i부터 j까지의 sum = sum[j+1] - sum[i];
    const sums = nums.reduce((acc, n, index) => {
        acc.push(acc[index] + n);
        return acc;
    }, [0]);
        
    const stack = []; // {index(시작), minValue}
    let answer = BigInt(0); 
    
    for(let index = 0; index < nums.length; index++){
        let lastIndex = index; 
        while(stack.length > 0 && stack[stack.length-1].minValue > nums[index]){
            // 현재 stack의 마지막의 value보다 현재 추가하려는 값이 작을때까지 반복
            const comp = stack.pop();
            lastIndex = comp.index;
  
            // comp.index부터, index까지가 comp의 minValue를 최솟값으로 가지는 subArray의 범위이다
            const minProduct = BigInt(comp.minValue) * BigInt(sums[index] - sums[comp.index]);
        
            if(answer < minProduct){
                answer = minProduct;
            } 
        }

        stack.push({index: lastIndex, minValue: nums[index]});
    }
    
    // 남은 것들 처리
    for(let i = stack.length-1; i>=0; i--){
        const comp = stack[i];
        const minProduct = BigInt(comp.minValue) * BigInt(sums[nums.length] - sums[comp.index]);
        if(answer < minProduct){
            answer = minProduct;
        }
    }
    
    
    return answer % modulo;
};

자바스크립트는 53비트까지 지원하지... 하는것을 다시 새길수 있었던 시간. prefix sum 부분도 BigInt 화해줘야하나했는데 문제조건에서 곱하더라도 64비트 미만이라고 보장을 해줘서 sum이 53비트를 넘지는 않겠구나하고 minProduct하는 부분만 BigInt처리를 해주었다. 숫자랑 섞이면 안된다는게 좀 낯설긴해서 다음에 다시 다루어 봐야할 type같다. 

 

 

2. 84. Largest Rectangle in Histogram: 21m01s58

https://leetcode.com/problems/largest-rectangle-in-histogram/

Largest Rectangle in Histogram - LeetCode

Stack을 통해서 히스토그램의 최대 직사각형을 구하는 문제는 굉장히 유명하다고 하는데, 제대로 이해해본적이 없어서 이번에 다시 시도해보았다. 이번엔 내 머리가 이해해주길.

 

https://www.youtube.com/watch?v=zx5Sw9130L0 

 

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    const stack = [];
    let answer = 0;
    
    for(let i = 0; i < heights.length; i++){
        let newIndex = i;
        while(stack.length > 0 && stack[stack.length - 1].height > heights[i]){
            const { startIndex, height } = stack.pop();
            newIndex = startIndex;
            
            const area = (i - startIndex) * height;
            if(answer < area){
                answer = area;
            }
        }
        
        stack.push({startIndex: newIndex, height: heights[i]});
    }
    
    for(let i = stack.length - 1; i >= 0; i--){
        const { startIndex, height } = stack.pop();
        const area = (heights.length - startIndex) * height;
        if(answer < area){
            answer = area;
        }
    }
    
    return answer;
};

1번문제를 이해했더니 2번은 똑같은 방식으로 풀수가 있었다. 

 

 

 

3. Trapping rainwater: 46m31s49

https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    const visited = new Set();
    
    const stackR = []; // 오른쪽 방향으로 체크
    let answer = 0;
    for(let i = 0; i < height.length; i++){
        if(stackR.length === 0 && height[i] === 0){
            continue;
        }
        
        if(stackR.length === 0){
            stackR.push({index: i, height: height[i], sum: 0});
            continue;
        }
        
       
        if(stackR[stackR.length - 1].height > height[i]){
            stackR[stackR.length - 1].sum += (stackR[stackR.length - 1].height - height[i]);
            continue;
        }
        
        // 크거나 같을때
        answer += stackR[stackR.length - 1].sum;
        visited.add(`${stackR[stackR.length - 1].index} ${i}`);
        stackR.pop();
        stackR.push({index: i, height: height[i], sum: 0});
    }
    
    // console.log(visited)
  
    const stackL = []; // 왼쪽 방향으로 체크
    
    for(let i = height.length-1; i >= 0; i--){
        if(stackL.length === 0 && height[i] === 0){
            continue;
        }
        
        if(stackL.length === 0){
            stackL.push({index: i, height: height[i], sum: 0});
            continue;
        }
        
        if(stackL[stackL.length - 1].height > height[i]){
            stackL[stackL.length - 1].sum += (stackL[stackL.length - 1].height - height[i]);
            continue;
        }
        
        // 크거나 같을때
        if(!visited.has(`${i} ${stackL[stackL.length - 1].index}`)){
            
            answer += stackL[stackL.length - 1].sum;
        }
        stackL.pop();
        stackL.push({index: i, height: height[i], sum: 0});
    }
    
    return answer;
};

스택 두개를 써서 오른쪽으로가면서 증가하는 방향일때 체크를 한번하고, 반대로 오면서 감소하는 방향일때 체크를 했다. set을 통해서 한번 체크했던 범위는 체크안하도록 뺏다. 메모리는 좀 많이 써브렀다. Stack을 reset해서 쓰면 더 적게 쓸것같다. 

조금 나아지긴한다. 

후기

드디어 물채우는 문제도 해결했다. 스택을 통해서 이런걸 할수있다니 하고 놀라운 시간이었다. 하나를 확실히 이해하고 나니까 두문제는 hard였는데도 풀수있었다.