두시간 알고리즘 - 2일차, 오늘은 LeetCode Weekly Context 240 푼다

오늘도...

https://leetcode.com/contest/weekly-contest-240

Contest - LeetCode

문제 풀이

 

1. 인구수 구하기 10m

https://leetcode.com/problems/maximum-population-year/

Maximum Population Year - LeetCode

전체를 순회해도 된다. 

/**
 * @param {number[][]} logs
 * @return {number}
 */
var maximumPopulation = function(logs) {
    let maxYear = 0;
    let maxValue = 0;
    for(let i = 1950; i <= 2050; i++){
        const population = logs.reduce((acc, p) => {
            if(p[0] <= i && i < p[1]){
                return acc+1;
            }
            return acc;
        } , 0);
        
        if(population > maxValue){
            maxYear = i;
            maxValue = population;
        }
    }
    
    return maxYear;
};

 

 

2. 숫자 쌍의 최대 거리 구하기: 13m27s34

https://leetcode.com/problems/maximum-distance-between-a-pair-of-values/

Maximum Distance Between a Pair of Values - LeetCode

non-increasing 비증가: x1 >= x2 >= x3 ....

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDistance = function(nums1, nums2) {
    let answer = 0;
    let count = 0;
    
    for(let i = 0; i < nums1.length; i++){
        let temp = 0; 
        
        for(let j = i + answer; j < nums2.length; j++){
            if(nums1[i] <= nums2[j]){
                temp = j - i;
            }else{
                break;
            }
        }
        
        if(answer < temp){
            answer = temp;
            count = 1;
        }else if(answer === temp){
            count++;
        }
    }
    
    return answer;
};

non-increasing인데다가 배열길이가 각각 10의 5승이라 이중 포문돌면 난리가 날거라는 생각은 했다. 

 

그래서 answer과 count 변수를 써서 이중 포문을 돌긴 돌되 중간에 내부 포문에 조건을 추가해서 다 순회하지 않도록 제어를 했다. 즉, 내부포문에 현재 maximum 길이보다 큰곳부터 인덱스를 검사하도록해서 maximum이 될수가 없는 부분을 걷어냈다. 그리고 count는 동일한 maximum value를 가진 쌍을 보일때 증가시키고, 새로운 max value가 나오면 1로 업데이트 하는 식으로 했다. 

 

이정도면 경험상 꽤 빠른편. 그이상은 가끔 돌리면 더 빠르게 나올때도 있고 그래서 뭔지 모르겠다. 

 

 

 

3. Maximum Subarray Min-Product - 30분쓰고 못품

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

Maximum Subarray Min-Product - LeetCode

modulo 처리를 해야하는데, 큰 숫자에 대해서 처리가 잘안되서 답을 봤다. 

 

- 망한 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumMinProduct = function(nums) {
    const modulo = Math.pow(10, 9) + 7;
    
    let answer = 0; 
    for(let i = 0; i < nums.length; i++){
        let sum = 0;
        let min = -1;
        
        for(let j = i; j < nums.length; j++){
            sum += nums[j];  
            if(min === -1){
                min = nums[j];
            }else{
                min = Math.min(min, nums[j]);         
            }
            if(min * sum > answer){
                answer = min * sum;
            }
        }
    }
    
    return answer % modulo;
};

- 정답 해설: 

- monotonous stack: https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/

monotone stack

 

- https://www.youtube.com/watch?v=c0yTVTI3qlk 

 

monotonic increasing stack: consider if each val was the min of subarray

 

우선 prefix sum을 구한다. 

right에는 index i를 기준으로 이 값보다 클때까지의 인덱스를 구한다. (index는 i보다 크다)

left: index i를 기준으로 이값보다 클때까지의 인덱스를 구한다(Index는 i보다 작다)

 

이때 right left의 인덱스를 구할때 stack을 사용할 수가 있다. 이렇게 해서 subarray길이를 최대로 만들수가 있다. 어차피 min은 자기 자신이니까. 일단 오늘은 풀이를 이해하는것까지! 내일 다시 풀어보자

 

 

 

후기

오늘 3번째 문제는 약간 stack을 잘 활용하지 못해서 개념만 감을 잡는데도 좀 걸려서 내일 stack문제를 진짜 다시 풀어보려고 한다.