https://www.acmicpc.net/problem/6198
사용한 알고리즘: 모노톤 스택(Monotone Stack)
풀이전략
https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/
먼저 문제를 풀기위해서는 monotone stack이라는 스택을 활용한 알고리즘을 알고 있어야 한다.
문제 풀이 전략으로 가장 쉽게 접근할 수 있는 방법은
이중 반복문을 사용해 특정 빌딩이 오른쪽에 있으면서 옥상을 볼 수 있는 빌딩 개수를 일일이 세는 방법이다.
하지만 이 방법은 시간 복잡도가 O(N^2)으로
빌딩의 개수가 최대 80,000개가 가능하기 때문에
최악의 경우 필요한 연산이 80,000*80,000= 6,400,000,000(64억)이다.
JAVA는 초당 1억번 연산하기 때문에 최악의 경우 약 64초가 걸려 시간 초과가 발생한다.
그런데 monotone stack의 시간 복잡도는 O(N)으로 획기적으로 시간을 절약할 수 있다.
이 문제에서 가장 중요한 아이디어는 특정 빌딩이 볼 수 있는 다른 빌딩의 개수를 세는 것이 아니라,
특정 빌딩을 바라볼 수 있는 건물들의 개수를 세어야 한다는 발상이다.
위와 같은 전략을 세웠을 경우, 이를 효과적으로 구현해 낼 수 있는 알고리즘이 monotone stack이다.
아래 그림은 스택에 입력받은 빌딩의 높이를 차례로 넣되,
만약 입력하기 전의 빌딩들 중 입력한 빌딩보다 높이가 낮은 빌딩이 있으면 스택에서 모두 pop한다.
그러면 하나의 입력으로 발생하는 변화하는 스택의 크기가
해당 빌딩을 바라볼 수 있는 빌딩의 개수가 된다.
따라서 각 과정마다의 스택 크기를 모두 더한 값을 출력하면 정답이 도출된다.
1) Stack에 1번 빌딩 높이인 10을 삽입 - 스택 사이즈 0 ( 자신은 제외한 사이즈)
2) Stack에 2번 빌딩 높이인 3을 삽입 - 스택 사이즈 1
...
6) Stack에 6번 빌딩 높이인 2를 삽입 - 스택 사이즈 1
제출코드
import java.io.*;
import java.util.Stack;
public class Main{
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int list[] = new int[N];
for(int i=0;i<N;++i){
list[i]=Integer.parseInt(br.readLine());
}
Stack<Integer> stack = new Stack<>();
long ansSum=0;
for(int i=0;i<N;++i){
while(!stack.isEmpty() && stack.peek()<=list[i]){
stack.pop();
}
ansSum+=stack.size();
stack.push(list[i]);
}
bw.write(ansSum+"\n");
bw.flush();
bw.close();
}
}
'알고리즘||코딩테스트 > DataStructure' 카테고리의 다른 글
[BOJ 1354] 무한 수열2 - JAVA, Gold5 (0) | 2023.08.29 |
---|