백준 오아시스 재결합 3015 자바

https://www.acmicpc.net/source/80479844

 

문제를 읽어보면, 서로 바라 볼 수 있는 사람의 쌍의 수를 구해야 한다.

조건은 두 사람 사이에, 둘중 아무나보다 키가 큰 사람이 존재하면 안된다는 것이다. ( 키가 동일하면 상관없다 )
처음엔 막연하게 이중포문을 생각했지만 N이 최대 50만 이기 때문에.. 절대 안된다 ! 

 

어렵다.. 머리 좋아지고 싶다..! 결국 보게 된 풀이..

 

스택을 사용한다. 

 

 

문제풀이 아이디어를 정리하면 다음과 같다.

1. 스택 만드는데 내림차순 스택임 (이유는 아래에)

2. 내림차순 스택을 만드는 과정에서 분기처리 잘하자

 

 

여기서 중요한점은 스택 내에  '앞으로 쌍이 될 가능성이 없는 사람' 은 제거한다.

 

예를들어 스택에 [3 2 1] 이 쌓여있다고 하자. 네번째에 키가 4인 사람이 들어왔다.

[3 2 1 4]가 된다. 네번째 사람은 첫번째~세번째 사람과 모두 쌍이 될 수 있다. 
근데 반대로 첫번째 ~ 세번째 사람은 네번째사람에게 가로막혀 앞으로 나올 사람들과 쌍이 절대 될 수 없다.

따라서 스택에서 제거한다.

 

다시 예를들어 [5 5 5]가 쌓여있다고하자. 네번째에도 키가 5인 사람이 들어왔다.

 

그럼 네번째 사람은 첫번째~세번째 사람과 모두 쌍이 될 수 있다. 근데 이걸 스택으로 어떻게 구현할것인가 ?

스택에 5 5 5 5 이렇게 쌓아두면 for문으로 5가 안나올때 까지 돌릴건가 ? 그건 시간초과다.

따라서 스택에 연속된 동일값은 하나만 저장해야한다. 그럴려면 연속된 동일값 개수를 카운트해야한다. 따라서 스택안의 타입은 인트배열로,  인트배열은 [키, 연속된 동일값 개수] 로 이루어진다.

 

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

public class Main {

    static int N;
    static Stack<int[]> stack = new Stack<>();
    static long answer;

    public static void main(String[] args) throws IOException {
        // N이 50만이기 때문에 웬만해선 O(N)이나 O(logN) 으로 해결해야함 . 
        // stack

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            // h => 키
            int h = Integer.parseInt(br.readLine());
            // cnt => 연속된 동일값 개수
            int cnt = 1;

            // 자신의 키와 스택에 쌓인 사람들의 키를 비교한다.
            // 만약 자신의 키가 스택에 있는 사람의 키보다 크다면 스택에서 사람을 지운다. (자신의 키가 더 크면 기존 스택에 있던 것들은 무용지물. 앞으로 나올 값들과 쌍이 될 수 없기 때문에 )
            // 스택은 내림차순으로 유지된다.
            while (!stack.isEmpty() && h > stack.peek()[0]) {
                int[] pop = stack.pop();
                answer += pop[1];
            }

            // 자신의 키와 스택에 있는 사람의 키가 같을 때.
            // 스택의 값을 없애고, 스택의 cnt만큼 현재 cnt에 추가한다.
            if (!stack.isEmpty() && h == stack.peek()[0]) {
                int[] pop = stack.pop();

                // 기존 스택 값을 없애기 때문에 answer에 더해준다.
                answer += pop[1];
                cnt += pop[1];
            }

            // 스택안에 사람이 있을 때. 쌍이 되므로 1을 더해줌
            if (!stack.isEmpty()) {
                answer++;
            }

            stack.push(new int[]{h, cnt});
        }

        bw.write(answer + "\n");
        bw.flush();
    }
}