[Platinum V] 오아시스 재결합 - 3015
성능 요약
메모리: 57688 KB, 시간: 464 ms
분류
자료 구조, 스택
제출 일자
2023년 10월 14일 20:08:45
문제 설명
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.
출력
서로 볼 수 있는 쌍의 수를 출력한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// 쌍의 개수
long count = 0;
Stack<Pair> stack = new Stack<>();
for (int i = 0; i < N; i++) {
int tmp = Integer.parseInt(br.readLine());
Pair pair = new Pair(tmp, 1);
// 작다면 pop해주고 같다면 횟수만큼 더해주어야 함
while (!stack.isEmpty() && stack.peek().height <= tmp) {
Pair top = stack.pop();
// 나온 횟수를 더 해줌
count += top.count;
// 값이 같다면 볼 수 있는 쌍들의 개수를 더해준다.
if (top.height == tmp) {
pair.count += top.count;
}
}
// 비어있지않다면 top에 있는 것과도 볼 수 있으므로 +1
if (!stack.empty()) {
count++;
}
stack.push(pair);
}
System.out.println(count);
}
static class Pair {
// 높이
int height;
// 나온 횟수
int count;
Pair(int height, int count) {
this.height = height;
this.count = count;
}
}
}
'알고리즘 - Baekjoon > Platinum' 카테고리의 다른 글
[Platinum V] 최솟값 찾기 - 11003 - JAVA[자바] (0) | 2023.10.14 |
---|