[Algorithm] 스택은 언제 쓸까? (ft. BOJ6198 옥상 정원 꾸미기 java)

민지·2024년 7월 30일

Algorithm

목록 보기

8/8

문제

옥상 정원 꾸미기

알고리즘 분류

스택
후입선출(Last In First Out) 자료구조이다.

굉장히 많이 나오는 유형이다.
코테 보면서 스택인가? 스러운 문제들은 한 방향에서 꺼내면서 값을 찾아나가는 문제가 많다. 최근 저장한 값이 쓸모가 있는 유형들.

스택은 언제 떠올릴까?

문자열을 가지고 한칸 한칸 제어하며 푸는 문제들: 스택, 큐, 덱

문자열을 가지고 한칸 한칸 제어하며 푸는 문제들 → 스택 자료구조 떠올리기 !!!!!

가장 마지막을 먼저 탐색하려는 스택의 성질이 문제에 보인다

BOJ 오큰수
- 오른쪽에 있어야 함 + 나보다 커야함 + 그 중 가장 왼쪽 << 이게 스택(늦게들어갔는데 젤 먼저탐색하잖아)
- 나보다 작으면 걔 빼고 내가 들어가 → 어차피 내 왼쪽은 내가 크면 그만임.
- 그럼 나보다 작은 이아이는 다시 쓰일 일이 없음 → 빼버려 → pop
- 이런 흐름으로 보면 스택이 제일 적합한 자료구조라고 할 수 있다.

참고) 스택 순회

스택 특성과 관계없이 앞에서부터 돈다.
1,3,5, .. 이렇게 들어가 있다면, pop()을 했을 땐 → 5 3 1 이지만
그냥 for 문으로 돌면 1 3 5 로 뽑힌다.

이는 Stack이 내부적으로 Vector를 상속받고 있으며, get 메소드를 통해 특정 인덱스의 요소에 접근할 수 있기 때문입니다.

접근 방법

스택을 활용함은 알겠고.. 구현이 중요한데 이 부분에서 주춤했다.

현재 기준 값이 있을 때, 나보다 오른쪽에 있는 빌딩만 확인하면 된다.

따라서 맨 오른쪽부터 순회하는 것이 효율적이다.

이 때 내 오른쪽 값들은 다음과 같이 분류된다.

나보다 작은 값
나보다 크거나 같은 값

여기서 나보다 크거나 같은 값을 만나면
그보다 오른쪽에 있는, 즉 그 이전에 순회한 값은 볼 필요가 없다.

스택

스택을 하나 두고, 현재 값보다 큰 값들만 넣는다.
현재 값보다 큰 값을 만날 때까지 반복한다.

즉, 스택의 값은 항상 오름차순 정렬이 되어 있다. 그리고 모든 값들은 한 번씩 스택에 들어간다.

cnt 배열: 현재 빌딩이 볼 수 있는 빌딩의 개수

스택에 들어간 값들은 cnt배열을 갱신한다.

코드

입력받는 값도 어차피 가장 끝부터 탐색하므로 스택에 넣어준다.
cnt의 인덱스가 빌딩들의 인덱스와 일치한다. 값은 볼 수 있는 빌딩의 개수
input이 총 80000개이고, 빌딩의 최대 높이가 10^9승이므로 long 타입으로 선언한다.

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

public class Main {

    static class Building {
        int idx;
        int height;

        Building(int idx, int height) {
            this.idx = idx;
            this.height = height;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Building> buildings = new Stack<>();
        Stack<Building> stack = new Stack<>();
        long[] cnt = new long[N+1];
        for (int i = 0; i < N; i++) {
            buildings.add(new Building(i + 1, Integer.parseInt(br.readLine())));
        }

        while(!buildings.isEmpty()) {
            Building now = buildings.pop();
            long tmpCnt = 0;

            while(!stack.empty()) {
                Building other = stack.peek();
                // 현재 높이가 더 크면 기존꺼 스택에서 빼고, 현재 볼수 있는 건물 카운팅 갱신
                if(now.height > other.height) {
                    // 기존 other가 볼 수 있었던 cnt수에 본인(+1)까지 카운팅한다.
                    tmpCnt += cnt[other.idx] + 1;
                    stack.pop();
                } else {
                    // 현재 높이가 작거나 같으면 벗어난다.
                    break;
                }
            }
            stack.push(now);
            cnt[now.idx] = tmpCnt;
        }

        long ans = 0;
        for(long n : cnt) {
            ans += n;
        }

        System.out.println(ans);
    }
}