6198번: 옥상 정원 꾸미기
문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으
www.acmicpc.net
바라보는 방향이 오른쪽이고, 그 방향에 자신보다 크거나 같은 높이의 건물과 그 이후의 건물의 옥상은 볼 수 없습니다.
저는 순차탐색으로 스택에 높이와 인덱스를 넣어가며 비교하였습니다.
먼저 s.peek의 높이가 현재 높이보다 작거나 같으면 자신 이후의 건물을 볼 수 없으므로 pop을 해줍니다.
이때 pop을 해주면서 현재의 인덱스와 삭제할 건물의 인덱스 사이에 존재하는 번호의 갯수를 ans에 더해줍니다.
이 작업이 끝나고 스택에 값이 남아있으면 s.peek()부터 작은 순서대로 pop이 될 것입니다.
s.peek()이 가장 마지막에 있는 건물이기 때문에 고정값(pre)으로 하고 pop하는 건물의 인덱스와 pre의 차이만큼 더해줍니다.
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 46 47 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static Stack<int[]> s = new Stack<>(); static int list[]; static int N; static long ans; static void func() { for (int i = 0; i < N; i++) { while (!s.isEmpty() && s.peek()[0] <= list[i]) { ans += (i - (s.peek()[1] + 1)); s.pop(); } s.push(new int[] { list[i], i }); } int pre = N - 1; while (!s.isEmpty()) { ans += (pre - s.peek()[1]); s.pop(); } System.out.println(ans); } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); list = new int[N]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); list[i] = Integer.parseInt(st.nextToken()); } } public static void main(String[] args) throws Exception { input(); func(); } } | cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 4889 안정적인 문자열 (0) | 2021.01.26 |
|---|---|
| boj 2504 괄호의 값 (0) | 2021.01.26 |
| boj 1874 수택 수열 (0) | 2021.01.25 |
| boj 17298 오큰수 (0) | 2021.01.25 |
| boj 4358 생태학 (0) | 2021.01.25 |