<BOJ>6198번: 옥상 정원 꾸미기
문제
접근
- 순차적으로 접근하되, 빌딩의 높이와 바라보는 방향(오른쪽)에 대한 조건을 고려할 것.
- 현재 빌딩에서 오른쪽으로 바라볼 때, 낮은 높이의 빌딩만 확인할 수 있다.
- 더 높거나 같은 높이의 빌딩이 있으면 다음 빌딩들이 가려짐
이 조건들을 고려해 Stack
을 활용하여 접근하면 쉽게 풀 수 있다.
내 코드
import java.io.*;
import java.util.Stack;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static Stack<Integer> stack = new Stack<>();
static int temp;
static long count;
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
temp = Integer.parseInt(br.readLine());
while (!stack.isEmpty() && stack.peek() <= temp) stack.pop();
count += stack.size();
stack.push(temp);
}
System.out.println(count);
}
}
- 스택에 빌딩의 높이를
push
하기 전엔 앞서 삽입된 빌딩의 높이와 매번 비교해야 함. - 스택에 담겨있는 빌딩의 개수를 통해 최종적인 결과를 도출할 수 있음.
PS 초보인 내 입장에선 스택이 PS에서 어떤식으로 쓰이는지 늘 궁금했었는데 이번 문제를 통해 조금이나마 정리를 하고있다.
// 바킹독님 감사해요...ㅎㅎ
Author And Source
이 문제에 관하여(<BOJ>6198번: 옥상 정원 꾸미기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@songs4805/BOJ6198번-옥상-정원-꾸미기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)