Algorithm - Programmers & LeetCode Problems 6

이소라·2023년 12월 4일
0

Algorithm

목록 보기
70/77

LeetCode Problem 739. Daily Temperatures

  • Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature.
    • If there is no future day for which this is possible, keep answer[i] == 0 instead.

Examples

  • Example 1:

    • Input: temperatures = [73,74,75,71,69,72,76,73]
    • Output: [1,1,4,2,1,1,0,0]
  • Example 2:

    • Input: temperatures = [30,40,50,60]
    • Output: [1,1,1,0]
  • Example 3:

    • Input: temperatures = [30,60,90]
    • Output: [1,1,0]

Constraints

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

Solution

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const totalLength = temperatures.length;
    const answer = new Array(totalLength).fill(0);
    const stack = [];

    for (let i = 0; i < totalLength; i++) {
        while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
            const index = stack.pop();
            answer[index] = i - index;
        }
        stack.push(i);
    }

    return answer;
};



LeetCode Problem 856. Score of Parentheses

  • Given a balanced parentheses string s, return the score of the string.

  • The score of a balanced parentheses string is based on the following rule:

    • "()" has score 1.
    • AB has score A + B, where A and B are balanced parentheses strings.
    • (A) has score 2 * A, where A is a balanced parentheses string.

Examples

  • Example 1:

    • Input: s = "()"
    • Output: 1
  • Example 2:

    • Input: s = "(())"
    • Output: 2
  • Example 3:

    • Input: s = "()()"
    • Output: 2

Constraints:

  • 2 <= s.length <= 50
  • s consists of only '(' and ')'.
  • s is a balanced parentheses string.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var scoreOfParentheses = function(s) {
    const stack = [0];
    const closeParentheses = ')';

    for (let i = 0; i < s.length; i++) {
        if (s[i] === closeParentheses) {
            let last = stack.pop();
            last = last === 0 ? 1 : last * 2;
            stack[stack.length - 1] += last;
        } else {
            stack.push(0);
        }
    }

    return stack[stack.length - 1];
};



Programmer Problem lev.2 석유 시추

  • 세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

  • 예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

  • 시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.
시추관의 위치획득한 덩어리총 석유량
1[8]8
2[8]8
3[8]8
4[7]7
5[7]7
6[7]7
7[7, 2]9
8[2]2
  • 오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

  • 석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
    • land[i][j]i+1j+1열 땅의 정보를 나타냅니다.
    • land[i][j]0 또는 1입니다.
    • land[i][j]0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
  • 정확성 테스트 케이스 제한사항
    • 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
    • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

입출력 예

  • 입력 : land = [[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]
  • 출력 : 16
  • 설명
    • 시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.
시추관의 위치획득한 덩어리총 석유량
1[12]12
2[12]12
3[3, 12]15
4[2, 12]14
5[2, 12]14
6[2, 1, 1, 12]16
  • 6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

Solution

function solution(land) {    
    const n = land.length;
    const m = land[0].length;
    const visited= new Array(n).fill().map(_ => new Array(m).fill(0));
    const oilMap = new Map();
    let maxOil = 0;
     let oilIndex = 1;
    
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    
    function bfs(rowIndex, colIndex) {
        const queue = [[rowIndex, colIndex]];
        let oilCount = 0;
        
        visited[rowIndex][colIndex] = oilIndex;
        
        while(queue.length) {
            const [x, y] = queue.shift();

            
            if (land[x][y]) {
                oilCount++;
            }
            
            for (let i=0; i<4; i++) {
                let nx = x + dx[i];
                let ny = y + dy[i];
                
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue;
                
                if (land[nx][ny]) {
                    visited[nx][ny] = oilIndex;
                    queue.push([nx, ny]);
                }
            }
        }
        
        oilMap.set(oilIndex, oilCount);
        oilIndex++;
        return oilCount;
    }
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (! visited[i][j]&& land[i][j]) {
                bfs(i, j);
            }
        }
    }

    for (let colIndex = 0; colIndex < m; colIndex++) {
        let oilSum = 0;
        const oilIndexSet = new Set();
        for(let rowIndex = 0; rowIndex < n; rowIndex++) {
            const oilIndex = visited[rowIndex][colIndex];
            if (oilIndex) {
                if (!oilIndexSet.has(oilIndex)) {
                    oilSum += oilMap.get(oilIndex);
                }
                oilIndexSet.add(oilIndex);
                
            }
        }
        
        maxOil = Math.max(maxOil, oilSum);
    }
    return maxOil
}

0개의 댓글