시작
처음엔 이렇게 생각했다.
- 지금 내가 서있는 위치를 기준으로, 나보다 높거나 같은 건물이 나올 때까지 내 오른쪽의 건물을 센다.
- 만약 나보다 높거나 같은 건물이 나오면, 다시 그 건물의 왼쪽 건물부터 하나씩 빼가며 그 건물의 이전 건물보다 더 높으면 세어온 횟수만큼 더해준다.
이게 그림으로 그려서 나온 과정이라 말로 잘 안옮겨지는데, 예시로 나온 [10, 3, 7, 4, 12, 1]를 놓고 설명해보자면
- 일단 10을 스택에 넣는다. (
[10]) - 이제 나(
10)보다 더 높거나 같은 건물이 나올 때까지 건물의 높이를 차례로 담아준다. ([10, 3, 7, 4]) - 나(
10)보다 더 높은 건물(12)이 나왔으니, 4, 7, 3, 10의 순서로 pop 한다.
3-1. 4의 경우 자기 오른쪽의 높이가 12이므로, 볼 수 있는 건물이 없다 (cnt: 0 -> 1, acc: 0 -> 0)
3-2. 7의 경우 자기 오른쪽의 높이가 4이므로, 이때까지 누적해온 건물의 수(cnt)만큼 답에 더해준다. (cnt: 1 -> 2, acc: 0 -> 1)
3-3. 3의 경우 자기 오른쪽의 높이가 7이므로, 볼 수 있는 건물이 없다. (cnt: 2 -> 3, acc: 1 -> 1)
3-4. 10의 경우 자기 오른쪽의 높이가 3이므로, 막힘 없이 12 전까진 볼 수 있다. (cnt: 3->4, acc: 1 -> 4)
3-5. 이제 12가 가장 높으므로, 12를 스택에 넣는다. ([12])
3-6. 2는 12보다 낮으므로, 스택에 넣는다. ([12, 2])
3-7. 남은 값들에 대해서도 동일한 과정을 거쳐, 2는 맨 오른쪽에 있으므로 볼 수 있는 건물이 없다. 따라서 그냥 pop해준다. ([12], cnt: 0 -> 1, acc: 4 -> 4)
3-8. 12의 경우 자기 오른쪽의 높이가 2이므로, 2를 볼 수 있다. ([], cnt: 1 -> 2, acc: 4 -> 5)
,,맞았으면 블로그에 글 쓰러 안왔겠지
반례
좀 생각해보다가 나온 반례인데, [10, 3, 7, 4, 8, 9]라면 어떨까?
- 최초로 스택에 들어간 10은 다른 나머지 값들보다 크기 때문에, 스택에는
[10, 3, 7, 4, 8, 9]가 쌓인다. - 이제 스택을 비워줘야 하는데, 같은 논리라면 맨 끝의 9가 볼 수 있는 건물은 없으니까 거기까진 맞다. (cnt: 0 -> 1, acc: 0 -> 0)
- 8도 맞다. 옆에 9가 있으므로. (cnt: 1 -> 2, acc: 0 -> 0)
- 4 역시 맞다. 옆에 8이 있으므로. (cnt: 2 -> 3, acc : 0 -> 0)
- 근데 7의 오른쪽에 4가 있다고 해서, 이때까지 누적된 cnt값, 즉 3을 그냥 더해준다는건 7이 4도 보고 8도 보고 9도 볼 수 있다는 의미이다. 이걸 생각을 못한건데,,
스택을 두 개 쓰는건가까지 생각하면서 한 삼일을 고민하다가 결국 GG치고 키워드를 찾아봤다. 이름하여 Monotone Stack,,!
Monotone Stack
모노톤 스택이란, 요소들이 증가하는 순서나 감소하는 순서로 유지되는 스택을 의미한다. 또한 동일한 요소가 반복될 수 없어 [2, 1, 1]이나 [1, 1, 2]와 같은 스택은 모노톤 스택이 아니다.
문제의 입력값으로 주어진 [10, 3, 7, 4, 12, 1]을 쌓이는 방향으로 감소하는 모노톤 스택을 만들어보자.
- 처음에 스택은 비어 있으므로 10은 그냥 들어간다.
[10] - 3을 넣어도 단조 감소 모노톤 스택의 조건을 만족한다.
[10, 3] - 7을 넣으려는데 7을 그대로 넣으면
[10, 3, 7]이므로, 앞의 7을 넣어도 단조 감소 모노톤 스택일 수 있도록 7보다 더 큰 10을 만날 때까지, 즉 3을 빼고 7을 넣어준다.[10, 7] - 4를 넣어도 단조 감소 모노톤 스택의 조건을 만족한다.
[10, 7, 4] - 12를 넣으려는데, 단조 감소 스택의 조건을 만족할 때까지 빼다보니 4, 7, 10 차례로 요소가 모두 날아가고
[12]가 되었다. - 1을 넣어도 단조 감소 모노톤 스택의 조건을 만족한다.
[12, 1]
해설
이 문제를 그냥 생각 없이 푼다면, 아까 스택 두 개니 뭐니 했던데서 알 수 있듯 각각의 건물에 대해서 오른쪽으로 이동하며 내가 더 볼 수 없는 높이가 나올 때까지 반복해주면 된다.
예를 들어서 10은 12를 만날 때까지 3, 7, 4, 12를 순회하고, 3은 7을, ... , 12는 1을 순회하는 식이다. 즉 O(N^2)의 시간 복잡도를 가진다는 말인데, 이러면 사실 스택을 쓰는 것도 아니다. 그냥 깡으로 반복문 두 번 돌아가는거지.
어떤 고수님의 설명(꼭 들어가서 다시 읽어봐야 한다!)으로 이런 문제에 이름이 붙어있다는걸 알게 되었는데, Find Next Greatest Number 문제라 부른다고 한다. 말 그대로 시퀀스 안에서 특정 수보다 큰 다음 숫자를 찾는 문제인데, 이 문제에서는 나보다 높이 있거나 같은 높이의 건물의 정원은 볼 수 없다고 되어 있으니 >이냐 >=이냐 차이만 있을 뿐 비슷한 문제라 할 수 있겠다.
우선 어떤 문제인지까지는 파악되었으니, 위에서 만든 모노톤 스택 만들기 과정을 다시 따라가며 의미를 되짚어보자.
- 처음에 스택은 비어 있으므로 10은 그냥 들어간다.
[10] - 3을 넣어도 단조 감소 모노톤 스택의 조건을 만족한다.
[10, 3] - 단조 감소 모노톤 스택의 조건을 만족하며 7을 넣으면
[10, 7]이 되는데, 이는 7보다 큰 다음 수가 10이라는 것으로 해석할 수 있다. - 4는 문제 없이 바로 넣을 수 있는데, 마찬가지로
[10, 7, 4]를 보면 4보다 큰 수는 다음 수는 7임을 알 수 있게 된다.
이걸 어떻게 써먹냐면, 2번 과정에서 3을 넣을 때 3보다 큰 건물이 10으로 하나가 있음을 스택의 사이즈만 보고 알 수 있다는 점을 활용할 수 있다. 스택의 크기를 구하는데 굳이 요소를 다 빼서 볼 필요 없이, 그냥 개수도 같이 기록해주면 되지 않는가? (a->b를 'a가 b를 볼 수 있다'고 한다면, 지금까지의 결과는 [10->3]이다. 모노톤 스택은 [10, 3], totalCnt=0+1)
이어서 3을 빼고 7을 넣는다는건, 3이 7을 볼 수 없음과 같고(그래서 단조 감소 모노톤 스택의 조건을 유지하고 있는 것!), 7을 넣기 전에 7보다 큰 건물이 10으로 하나가 있음을 이번에도 한 번에 알 수 있다. (결과는 [10->3, 10->7], 모노톤 스택은 [10, 7], totalCnt=1+1)
4는 그대로 들어갈 수 있는데, 이는 스택의 꼭대기에 있는 7보다 작기 때문이며 단조 감소 모노톤 스택의 조건을 만족하기 때문에 스택 안쪽에 어떤 값이 있는지는 몰라도 나보다 높은 위치에 있음을 알 수 있다는 뜻이다. (결과는 [10->3, 10->7, 10->4, 7->4], 모노톤 스택은 [10, 7, 4], totalCnt=2+2)
대망의 12! 12는 이제까지 봤던 어떤 건물보다 크기 때문에 모노톤 스택의 조건을 만족하려면 앞에 있던 값들을 다 빼줘야 한다. (결과는 그대로 [10->3, 10->7, 10->4, 7->4], 모노톤 스택은 [12], totalCnt=4+0)
1은 pop 없이 스택에 추가할 수 있으므로, 결과는 [10->3, 10->7, 10->4, 7->4, 12->1], 모노톤 스택은 [12, 1]이 된다., totalCnt=4+1=5)
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
public class Main {
static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static final StringBuilder out = new StringBuilder();
static int NUM_OF_BUILDINGS;
static int[] heights;
static long solution() {
// 건물들이 내려다 볼 수 있는 건물들의 수의 합
long watchableCnt = 0;
// 단조 감소 모노톤 스택
ArrayDeque<Integer> heightStack = new ArrayDeque<>();
// 요소 1개만 있으면 무조건 모노톤 스택
heightStack.push(heights[0]);
// 두번째 건물부터,
for (int building = 1; building < NUM_OF_BUILDINGS; building++) {
int height = heights[building];
// 모노톤 스택의 조건을 만족하도록 지금 높이보다 작은 높이를 모두 pop 해줌
while (!heightStack.isEmpty() && height >= heightStack.peek()) {
heightStack.pop();
}
// 핵심!! 스택에 나보다 큰 높이만 남았으므로, 그 높이에서만 나를 볼 수 있음
watchableCnt += heightStack.size();
// 가장 작은 요소로써 스택에 포함됨
heightStack.push(height);
}
return watchableCnt;
}
public static void main(String[] args) throws Exception {
NUM_OF_BUILDINGS = Integer.parseInt(in.readLine());
heights = new int[NUM_OF_BUILDINGS];
for (int building = 0; building < NUM_OF_BUILDINGS; building++) {
heights[building] = Integer.parseInt(in.readLine());
}
out.append(solution());
System.out.println(out);
}
}참고한 글
