BOJ_3015_오아시스 재결합

[Platinum V] 오아시스 재결합 - 3015

문제 링크

성능 요약

메모리: 60024 KB, 시간: 432 ms

분류

자료 구조, 스택

제출 일자

2024년 8월 23일 10:42:10

문제 설명

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 2³¹ 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {

	/**
	 * height : 키
	 * num : 같은키 가진 연속된 사람 수
	 */
	static class Person {
		int height;
		int pairNum;

		public Person(int height, int pairNum) {
			this.height = height;
			this.pairNum = pairNum;
		}
		
	    @Override
	    public String toString() {
	        return "(" + height + "," + pairNum + ")";
	    }
	}

	static BufferedReader br;
	static int N, arr[];
	static long ans;
	static Stack<Person> stack;

	public static void main(String[] args) throws Exception {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		stack = new Stack<>();

		int i;
		for (i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		/**
		 * 지금 사람보다 키가 작은 사람들은 모두 볼 수 있으므로 볼 수 있는 쌍의 수 추가하고 스택에서 제거.
		 * 자신보다 큰 사람은 1명만 볼 수 있음
		 * 최종적으로 스택에는 키가 중간중간 작은애들 빠지고 내림차순으로 남을것이다.
		 * 시간복잡도 O(N)
		 */
		
		long cnt = 1;
		int j;
		for (j = 0; j < N; j++) {
			int tmp = arr[j];
			int tmpNum = 1;

//	        System.out.println("\n처리 중인 사람: 키 " + tmp);
//	        System.out.println("처리 전 스택: " + stack);
	        
			// 현재 사람보다 키가 작은 사람들을 스택에서 제거하며 쌍의 수 추가
			while (!stack.isEmpty() && tmp > stack.peek().height) {
				ans += stack.peek().pairNum;
				stack.pop();
//	            System.out.println("팝: " + stack.pop() + ", ans = " + ans);

			}
			
			// 남은 자신보다 크거나 같은 사람들
			if (!stack.isEmpty()) {
				if (stack.peek().height == arr[j]) { // 같은 키
					ans += stack.peek().pairNum;
					tmpNum = stack.peek().pairNum + 1;
					if (stack.size() > 1)
						ans++;
					stack.pop();
//	                System.out.println("같은 키 처리: " + stack.pop() + ", ans = " + ans + ", tmpCnt = " + tmpNum);

				} else {  // 자신보다 큰 사람
					ans++;
//	                System.out.println("큰 사람 처리: ans = " + ans);

				}
			}
			stack.push(new Person(arr[j], tmpNum));
//	        System.out.println("푸시 후 스택: " + stack);

		}
		System.out.println(ans);
	}
}