[백준] 옥상 정원 꾸미기 6198

문제 링크 : https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

public class GardenOn_6198 {
    public static int findNumber(int build[]) {
        int ans = 0;
        int len = build.length;
        for (int i = 0; i < len; i++) {
            int tmp = build[i];
            for (int j = i+1; j < len; j++) {
                if(tmp>build[j]) {
                    ans+= 1;
                } else {
                    break;
                }
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int build[] = new int[N];
        for (int i = 0; i < N; i++) {
            build[i] = sc.nextInt();
        }
        System.out.println(findNumber(build));
    }
}

처음에는 단순하게 for문을 돌아서 체크를 하면 된다고 생각했는데 생각해보니 시간 복잡도가 O(N^2)로 너무 많이 걸렸다.

그리고 조건이 지금 숫자가 크니까 long 타입으로 배열을 변경해봐야 겠다. 

 

그래서 일단 생각을 우선 해봤는데... 자료구조 중에서 하나를 사용하면 어떨까 하는 생각이 들었다. 

일단 입력을 받은 배열을 for문을 통해 하나씩 탐색하면서 세보고 -> 오른쪽만 보기 때문에 작은 인덱스는 탐색할 필요가 없음 

: 현재 탐색하는 인덱스를 하나 정하고 -> build[idx]에서 하나씩 늘려가면서 탐색을 한 뒤 -> 만약 큰게 나오면 stack이 빌 때 까지 pop()을 해서 -> 갯수를 세면 어떨까 하는 생각이 들었다.