문제 - 옥상 정원 꾸미기
문제
도시에는 N개의 빌딩이 있다.
빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.
i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.
i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.
예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우
=
= =
= - =
= = = -> 관리인이 보는 방향
= - = = =
= = = = = =
10 3 7 4 12 2 -> 빌딩의 높이
[1][2][3][4][5][6] -> 빌딩의 번호- 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
- 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
- 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
- 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
- 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.
- 따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.
입력
첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)
출력
각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.
입력 예시 1
6
10
3
7
4
12
2
예제 출력 1
5접근방식
Stack의 LIFO를 활용해서 누적되어 있는 빌딩을 계산하는 방식
이 문제는 실제로 코딩테스트에서 여러번 봤던 유형이다. 그 때마다, 시간 복잡도를 고려하지 않고 이중 for문을 돌렸다. 하지만 주어진 조건을 보면 이중 for문을 쓰면 바로 시간초과가 난다.
그래서 한번의 전체 탐색으로 계산을 할 수 있는 방식이 필요했다.
이 문제는 각 빌딩마다 벤치마킹 하는 빌딩의 수로 계산하려고 하면 어렵다.
생각의 전환으로, 각 빌딩이 벤치마킹 당한 갯수를 생각해야한다. i번째 빌딩에서 이전에 나보다 더 높은 빌딩의 갯수를 누적 계산하는 방식이다.
주어진 예제로 예시를 들면,
- 1번 빌딩은 아무에게도 벤치마킹이 되지 않는다.
- 2번 빌딩은 1번 빌딩에게 벤치마킹 된다.
- 3번 빌딩은 1번 빌딩에게 벤치마킹 된다. (2번 빌딩은 본인보다 낮으므로 배제한다.)
- 4번 빌딩은 1번,3번 빌딩에게 벤치마킹 된다.
- 5번 빌딩은 아무에게도 벤치마킹 되지 않는다.
- 6번 빌딩은 5번 빌딩에게 벤치마킹 된다.i번째 빌딩을 조회 할 때, 나보다 이전에 낮은 빌딩이 있으면 삭제하는 방식, 즉 Stack을 활용하여 stack.peek()가 현재 h값보다 낮을 경우 pop하는 방식으로 구현하면 된다.
정답코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
static int N;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Stack<Long> buildings = new Stack<>();
buildings.push(Long.parseLong(br.readLine()));
long count = 0;
for(int i=0;i<N-1;i++) {
Long now = Long.parseLong(br.readLine());
while(!buildings.isEmpty() && buildings.peek()<=now) {
buildings.pop();
}
buildings.add(now);
count+=buildings.size()-1;
}
System.out.println(count);
}
}이문제를 풀고 배운 점
- 시간 복잡도를 고려해야할 경우, 각각의 자료구조 특징을 생각하자
- Stack이 DFS에서만 사용되는 것은 아니니, 여러 상황에서 선택지로 고려해보자
