[BOJ] 백준 3015번 오아시스 재결합 (Java)

#3015 오아시스 재결합

난이도 : 골드 1

유형 : 자료구조 / 스택 

3015번: 오아시스 재결합

▸ 문제

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

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

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

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

▸ 입력

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

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

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

▸ 출력

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

 

문제 풀이  

스택을 활용하여 각 조건에 따라 쌍을 매칭해주면 된다. 분기만 잘해주면 된다.

 

0. 먼저 stack이 비어있지 안으면 기존에 stack에 저장되어 있는 값 중에 자신보다 낮은 키를 가진 사람들과 매칭해준다.

• 매칭해준다음 낮은 키의 데이터는 삭제한다. 왜냐하면 현재 새로 저장되는 키 때문에 그 건너에 있는 사람을 볼 수 없기 때문이다

 

1. stack이 비어있는 경우

• 새로운 사람의 키 데이터를 추가한다.

2. stack이 비어있지 않은 경우

• 2-1) 새로운 사람의 키가 가장 가까이에 있는 사람보다 키보다 작을 경우
  • 서로 쌍을 맺어주고 값을 더해준다. 왜냐하면 기존의 사람보다 키가 작기 때문에 기존에 있는 사람은 다음 사람과도 쌍을 이룰 수 있기 때문이다.
• 2-2) 새로운 사람이 가장 가까이에 있는 사람보다 키가 같은 경우
  • 키가 같은 사람끼리 연결해주고 stack에 저장된 해당 키의 카운트를 늘려준다.
  • 그리고 기존의 가장 큰 사람과도 연결을 맺어준다. 

 

 

	과정 1	stack	과정2	stack	result
push2	1번과정 진행 push(2)	2	-	-	0
push4	0번 과정 진행 (2,4) 매칭 후 2 삭제	0	1번 과정 진행 push(4)	4	1
push1	2-1)번 과정 진행  (4,1) 매칭	1, 4	-	-	2
push2	0번 과정 진행 (1, 2) 매칭 후 1 삭제	2, 4	2-1)번 과정 진행 (2,4) 매칭	2, 4	4
push2	2-2)번 과정 진행 (2,2) 매칭 후 2의 카운트 증가	2(2), 4	2-2)번 과정 진행 (2, 4) 매칭	2(2), 4	6
push5	0번 과정 진행 (2(2), 5) 매칭 (4, 5) 매칭	0	1번 과정 진행 push(5)	5	9
push1	2-1)번 과정 진행 (5,1) 매칭	5,1	-	-	10

 

풀이 코드 

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));
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		long result = 0;
		Stack<int[]> s = new Stack<>();
		for(int i=0; i<n; i++) {
			while(!s.isEmpty() && s.peek()[0] < arr[i]) {
				result+= s.pop()[1];
			}
			
			if(s.isEmpty()) {
				s.push(new int[] {arr[i],1});
			}else {
				if(s.peek()[0] > arr[i]) {
					s.push(new int[] {arr[i],1});
					result++;
				} else {
					result+= s.peek()[1]++;
					if(s.size()>1) result++; 
				}
			}
		}
		System.out.println(result);
	}
}