[백준] 6198

 

빌딩을 순차적으로 세워놨다고 가정하면 80,000 ~ 1 까지 총합을 구해야하고 그 값은 32억을 넘어간다.

따라서 int가 아닌 long 선언!

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        long cnt=0;
        int[] height = new int[num];
        for (int i=0; i<num; i++) {
            height[i] = scan.nextInt();
        }
        for (int i=0; i<num-1; i++) {
            for (int j=i+1; j<num; j++) {
                if (height[i]>height[j]) {
                    cnt ++;
                }
                else break;
            }
        }
        
        System.out.println(cnt);
    }
}

2중 반복문을 통해 해당 문제를 풀 수 있지만 자료구조를 활용해보자!

 

관점을 바꿔서 생각해보면 스택을 이용해 반복을 줄일 수 있다.

 

스택이 비어있지 않은동안 반복

1. 빌딩의 높이를 받고 자신보다 낮은 건물이 스택에 들어있는지 확인하고 만약 자신보다 낮은 건물이 스택에 들어있다면 모두 스택에서 제외한다.
2. 현재 스택에 남아있는 건물들( 나보다 높은 건물들 )의 갯수를 누적합에 더한다
3. 자신의 건물을 스택에 넣는다.

 

 

즉 다음 건물이 스택에 들어올때 본인보다 큰 건물의 개수를 누적 카운팅한다.

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        long cnt=0;
        for (int i=0; i<num; i++) {
            int height = scan.nextInt();
        
            while (!stack.isEmpty()) {
                if (stack.peek() <= height) {
                    stack.pop();
                }
                else {
                    break;
                }
            }
            cnt += stack.size();
            stack.push(height);
        }
       
        System.out.println(cnt);
    }
}

 

스택을 사용해서 푼 속도가 3배정도 빠르다 ..