workspace/algorithm
[Java/Stack] 정올 1141. 불쾌한 날
HwangJerry
2024. 2. 8. 09:30
JUNGOL
code_blocks 코드 보기
jungol.co.kr
풀이
stack을 사용하면 "stack을 한번 거친 소는 다신 들어올 수 없으므로" 넣는거 N번, 빼는거 N-1번 해서 O(N + N - 1번)의 연산만으로 해결이 가능하다.
코드
package algorithm.jol;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* 수행 시간 : 209ms
* 메모리 : 43.4 MB
*/
public class JOL_1141_불쾌한날 {
public static void main(String[] args) throws IOException {
Deque<Integer> st = new ArrayDeque<>();
long ans = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
while (!st.isEmpty() && st.peek() <= num) {
st.pop();
}
ans += st.size();
st.push(num);
}
System.out.println(ans);
}
}