백준/3015/Java - 오아시스 재결합
문제
https://www.acmicpc.net/problem/3015
3015번: 오아시스 재결합
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람
www.acmicpc.net
사람들이 줄을 설 때, 두 사람이 서로 볼 수 있는 쌍의 수를 구하는 문제이다.
줄을 설 때, 뒷 사람이 앞 사람보다 키가 크다면, 앞 사람은 뒤에 어떤 사람이 오더라도 그 사람을 볼 수 없다.
(문제의 조건 : 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.)
따라서 뒤에 나보다 큰 사람이 들어오면 나는 더 이상 줄에 서 있을 필요가 없으니 줄에서 퇴장하면 된다.
반대로 나보다 작은 사람이 들어오면? 나는 그 사람 뒤에 오는 사람도 볼 수 있으니 줄에서 나갈 필요가 없다.
처음에는 이렇게 단순하게만 생각해서, 숫자를 입력받아 스택에 넣고, 새로 입력받은 숫자가 스택의 최상단보다 크면 스택에서 빼는 식의 로직을 짜면 될 것이라고 생각했다. 하지만 뒤에 줄을 서는 사람이 키가 같은 경우, 눈을 마주친 쌍은 어떻게 계산할 것인지 생각하느라 어려웠던 문제.
줄을 선다 = 스택에 들어가는 행위
입력을 받는 숫자 = 새로 줄을 서야하는 사람의 키
스택의 맨 위 숫자 = 줄의 가장 뒤에 있는 사람의 키
새로 줄을 서는 사람이 줄의 가장 뒤에 있는 사람보다 크다면?
앞서 말했듯, 가장 뒤에 있는 사람은 더 이상 다른 사람과 눈을 마주칠 수 없으므로 줄에서 나가면 된다.
-> 스택에서 pop하고
왜냐하면 나가는 사람과 새로 들어오는 사람은 바로 중간에 장애물이 없기 때문에 둘은 눈을 마주볼 수 있기 때문이다.
-> 눈을 마주쳤으니 카운트(쌍의 개수)를 +1 하면 된다.
그럼 방금 나간 사람 뒤에 있던 사람은? 이 사람도 만약 새로 들어오는 사람보다 작다면 줄에서 나가도 된다.
-> 반복하면 된다. 앞에 남아 있는 사람이 없거나 새로 줄을 서는 사람보다 작지 않을 때까지.
새로 줄을 서는 사람이 줄의 가장 뒤에 있는 사람보다 작다면?
만약 사람들이 계속 나가다가, 새로 들어오는 사람보다 큰 사람이 줄에 나타났다면? 그 때 줄에 서면 된다
-> 스택에 넣어준다.
그리고 그 사람과도 눈을 마주칠 수 있게 된다. (중간에 사람이 없으니까)
-> 눈을 마주쳤으니 카운트(쌍의 개수)를 +1 하면 된다. 단, 앞에 사람이 있을 때이므로 스택이 비어있어선 안된다.
새로 줄을 서는 사람이 줄의 가장 뒤에 있는 사람과 키가 같다면?
이 경우에는, 새로 들어오는 사람이 가장 뒤에 있는 사람을 윷놀이 말처럼, 업는다고 생각하면 된다.
자리만 비켜주고 업히는 이유는 키가 같은 두사람 A와 B가 연속해서 서 있을 때, 그 뒤에 더 큰 사람 C가 줄을 선다면,
A와 B는 모두 C와 눈을 마주치고 나가야 하기 때문이다.
-> 더 큰 사람이 와서 스택에서 pop을 하지만 카운트는 1이 아니라 2 (두명이 한 자리에 있으니까)가 증가하게 된다.
-> 이를 위해서는 키와 사람의 수를 필드로 갖는 사람 객체를 구현하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
Stack<Person> stack = new Stack<>();
long ans = 0;
for(int i=0; i<N; i++) {
int height = Integer.parseInt(br.readLine());
Person person = new Person(height, 1); //줄에 입장 시작.
while(!stack.isEmpty() && stack.peek().height <= height) {
Person last = stack.pop(); // 줄의 가장 맨 뒷 자리 퇴장.
ans += last.cnt; // 줄에 입장하는 사람과 눈이 마주쳤으므로 쌍이 증가
if(last.height == person.height) person.cnt += last.cnt; //키가 같으면 업기.
}
if(!stack.isEmpty()) ans++; //줄에 입장할 때, 줄이 비어있지 않다면 앞사람과 눈이 마주치므로 쌍이 하나 추가
stack.push(person); //줄에 입장 완료.
}
sb.append(ans);
System.out.println(sb);
}
static class Person{
int height, cnt;
Person(int height, int cnt){
this.height = height; //키
this.cnt = cnt; //몇명인지, 즉 cnt가 2면 같은 키인 사람이 연속 두명인 것. 즉 한명이 업혀 한자리에 두명이 서있다.
}
}
}