(3015) 오아시스 재결합 (Java)

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

7
2
4
1
2
2
5
1

예제 출력 1

10

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Croatian Olympiad in Informatics 2007 1번

문제를 번역한 사람: baekjoon

알고리즘 분류

자료 구조
스택

Solution

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

public class Main {
    public static int n;
    public static long cnt;
    public static class Node {
        int h, cnt;
        Node(int h, int cnt) {
            this.h = h;
            this.cnt = cnt;
        }
    }
    public static Stack<Node> stk;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        stk = new Stack<Node>();

        for(int i = 0; i < n; i++) {
            int height = Integer.parseInt(br.readLine());
            Node cur = new Node(height, 1);

            while(!stk.isEmpty() && stk.peek().h <= height) {
                Node top = stk.pop();
                cnt += top.cnt;
                if(top.h == height) {
                    cur.cnt += top.cnt;
                }
            }

            if(!stk.isEmpty()) {
                cnt++;
            }

            stk.push(cur);
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

Feedback

스택 문제는 특히 생각해내는게 어려운것 같다. 이번 문제도 구글링의 도움을 받았다...
반복문을 돌면서 스택에 push 되는 원소의 관점에서 생각해보는 습관을 길러야할 것 같다.
이 문제에서도 줄을 서는 사람의 관점에서 그 앞에 사람들이 키 내림차순으로 줄을 서있을 경우 서로 마주볼 수 있게 되는 원리를 이용했다.