[Java, JS, Python]_6198_옥상 정원 꾸미기

hanseungjune·2023년 7월 15일
0

알고리즘

목록 보기
26/33
post-thumbnail

자바

import java.io.*;
import java.util.*;
public class decorating_the_rooftop_garden_6198 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] buildings = new int[N];
        for(int i=0;i<N;i++){
            buildings[i]= Integer.parseInt(br.readLine());
        }

        Stack<Integer> stack = new Stack<>();
        long count = 0;

        for(int b : buildings) {
            while(!stack.isEmpty() && stack.peek() <= b) {
                stack.pop();
            }
            stack.push(b);
            count += stack.size() - 1;
        }
        System.out.println(count);
    }
}

로직 설명

이 코드는 "옥상 정원 꾸미기" 문제를 해결하는 자바 코드입니다. 문제의 목표는 각 건물에서 보이는 다른 건물들의 수를 셉니다.

주요 사항은 각 건물이 자신보다 높은 건물이 나올 때까지의 건물들만 볼 수 있다는 점입니다. 이 점 때문에 각 건물이 어느 건물까지 볼 수 있는지 계산하려면 스택이 유용하게 사용됩니다.

먼저, 건물의 수(N)를 입력받습니다.

그런 다음 각 건물의 높이를 입력받아 배열에 저장합니다.

스택을 생성하고, 건물을 볼 수 있는 총 수를 나타내는 count 변수를 선언합니다.

각 건물에 대해 다음을 수행합니다:

  • 스택이 비어있지 않고, 스택의 맨 위에 있는 건물의 높이가 현재 건물의 높이 이하인 경우, 스택의 맨 위에 있는 건물을 제거합니다. 이는 현재 건물보다 높이가 낮은 건물들은 더 이상 보이지 않기 때문입니다.

  • 현재 건물의 높이를 스택에 넣습니다.

  • 현재 건물이 볼 수 있는 건물의 수를 계산하여 count에 더합니다. 이는 스택의 크기에서 1을 뺀 값과 같습니다. 1을 빼는 이유는 현재 건물이 자신을 제외한 다른 건물들만 볼 수 있기 때문입니다.

마지막으로 count를 출력합니다. 이는 각 건물이 볼 수 있는 건물들의 총 수입니다.

이 코드는 스택을 이용하여 각 건물이 볼 수 있는 건물들을 효율적으로 계산합니다. 건물의 높이를 스택에 넣어 높이가 낮은 건물들을 제거하면서 볼 수 있는 건물의 수를 계산합니다.

노드

const fs = require("fs");

const input=fs.readFileSync('/dev/stdin').toString().trim().split('\n').map((line) => line.trim()).map(Number);
const [n, ...buildings] = input;

let count = 0
let stack = []
for (b of buildings) {
    while (stack.length > 0 && stack[stack.length-1] <= b ) {
        stack.pop()
    }
    stack.push(b)
    count += stack.length - 1
}

console.log(count)

파이썬

import sys
input = sys.stdin.readline

N = int(input())
buildings = [int(input()) for _ in range(N)]

stack = []
count = 0

for b in buildings:
    while stack and stack[-1] <= b:
        stack.pop()
    stack.append(b)
    
    count += len(stack) - 1
    
print(count)
profile
필요하다면 공부하는 개발자, 한승준

0개의 댓글