[BOJ] 6198.옥상 정원 구미기(stack).java

#. Problem

https://www.acmicpc.net/problem/6198

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

N의 범위가 1 ≤ N ≤ 80,000 이라서

naive하게 풀면 시간복잡도가 O(N), 1,600,000,000 이 되어버리고

뻥.. 터질 것이다.

여기서 stack 자료구조를 사용한다면

생각보다 수월하게(?) 풀릴 것이다.

빌딩의 높이를 stack에 넣으면서

if 현재 빌딩의 높이가 

stack의 top보다 높이가 작으면 push 해주고 stack.size() - 1 을 누적

if 현재 빌딩의 높이가 

stack의 top보다 높이가 높거나 같으면 현재 빌딩보다 큰 빌딩이 나올 때까지 stack.pop() 을 해준 후

push 해주고 stack.size() - 1 을 누적해준다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack;   public class BOJ6198 {       static int N;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         N = Integer.parseInt(br.readLine());         int[] building = new int[N];         for (int i = 0; i < N; i++) {             building[i] = Integer.parseInt(br.readLine());         }           System.out.println(process(building));     }       private static long process(int[] building) {                  long res = 0;         Stack<Integer> stack = new Stack<>();         // 1. 초기 빌딩 정보를 넣고 시작         stack.add(building[0]);         for (int i = 1; i < N; i++) {             // 2. top 보다 작으면 push             if (building[i] < stack.peek()) {                 stack.add(building[i]);                 res += stack.size() - 1;             } else {                 while(!stack.isEmpty() && building[i] >= stack.peek())                     stack.pop();                 stack.add(building[i]);                 res += stack.size() - 1;             }         }                  return res;             }   }   Colored by Color Scripter

cs