백준 3015 오아시스 재결합 Java

알고리즘 분류에 스택으로 분류되어 있는 오아시스 재결합 문제이다.

 

문제를 간단히 설명하면

사람 수 N이 주어지고 N명의 사람들의 키가 순서대로 주어진다.

이 순서대로 줄을 서있을 때 A와 B가 마주 볼 수 있는 경우의 수를 출력하면 된다.

A와 B 사이에 A 또는 B보다 큰 사람이 있으면 안 된다.

 

N이 500,000이기 때문에 O(N^2)으로 비교해가면서 풀 수 없는 문제이다.

스택을 활용해야 한다는 힌트를 알았기 때문에

주어진 키를 전부 스택에 넣고 어떻게 활용하면 O(N)만에 풀 수 있을까

고민했는데 답이 안 나왔다.

 

답이 안 나온 이유는 주어진 키를 전부 스택에 넣었기 때문이다.

이 문제는 키를 하나씩 스택에 넣어가며 풀어야 된다.

for문을 돌면서 i번째 사람보다 i+1번째 사람이 키가 큰 경우 

i+1부터 그다음 사람들은 모두 i번째 사람과 마주 볼 수 없다는 점을 이용하면

O(N)만에 풀 수 있다.

 

푸는 방법을 설명하는 글을 몇 번이나 썼다 지웠다 했지만

이 문제는 코드가 간단하기 때문에 코드를 보면서 이해하는 게 빠를 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Q3015 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Stack<Pair> s = new Stack<>();
        long ans = 0;
 
        for(int i=0; i<n; i++) {
            int k = Integer.parseInt(reader.readLine());
            Pair p = new Pair(k, 1);
            while(!s.isEmpty()) {
                if(s.peek().x <= p.x) {
                    ans+= s.peek().y;
                    if(s.peek().x == p.x){
                        p.y += s.peek().y;
                    }
                    s.pop();
                } else {
                    break;
                }
            }
            if(!s.isEmpty()) {
                ans += 1;
            }
            s.push(p);
        }
        System.out.println(ans);
    }
}
class Pair{
    int x; //키
    int y; //키가 같은 사람
 
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

주어질 수 있는 키의 범위가 2^31 미만이고 N이 오십만 이하 이기 때문에

마주 볼 수 있는 경우의 수가 int의 범위를 넘을 수 있다.

때문에 정답을 저장할 변수는 꼭 long으로 자료형을 지정해야 한다.