[백준 3015] 오아시스 재결합

문제 링크 : https://www.acmicpc.net/problem/3015

이 문제는 오큰수 문제(https://velog.io/@gale4739/%EB%B0%B1%EC%A4%80-17298-%EC%98%A4%ED%81%B0%EC%88%98Java) 풀이와 유사하게 스택을 이용하여 풀 수 있습니다.

문제의 만족 조건, 즉 두 사람 사이에 키가 큰 사람이 없다는 말은 반대로 말하면 자신의 오른쪽에 있는 수 중 큰 수 중에 가장 가까운 수와의 거리를 구하는 문제입니다. 따라서 기존 오큰수의 알고리즘과 유사한 방식으로 진행됩니다.

하지만 오큰수 알고리즘과 차이점이 3가지 존재합니다.

1. 오큰수의 경우 "값"을 출력하기 때문에 미리 리스트에 값을 저장한 후 인덱스를 이용해서 반복문을 돌려 해당 위치의 값을 바꾸는 방식이었다면, 이 경우는 오큰수와 자기 자신 사이의 "거리"를 구하는 것이므로 값을 저장하지 않고 하나씩 읽어오면서 인덱스가 아니라 값을 기준으로 비교할 수 있습니다.

2. 오큰수의 경우 가장 오른쪽에 있는 값은 참조할 대상이 없습니다. 하지만 이 문제의 경우 가장 오른쪽에 있는 값도 왼쪽 방향으로 참조가 가능해야 합니다. 이를 보정하기 위해 스택에 값이 존재한 상태에서 반복문을 탈출했다면 자신보다 작은 수가 그 다음에 존재하는 것으로 판단할 수 있기 때문에 정답을 1 더해줍니다.

3. 오큰수의 경우 "두 값이 같을 경우" 무시합니다. 하지만 이 경우 값이 같을 경우 서로 마주볼 수 있기 때문에 같이 고려를 해주어야 합니다. 값이 같을 경우 서로 마주보는 것으로 판정되기 때문에 반복문 내부에는 들어와야 합니다. 하지만 그대로 막히는 것이 아니라 뒤의 오큰수까지 참조가 가능하기 때문에 반복문 내에서 cnt값을 누적하여 한번에 묶어서 값을 처리하는 목적으로 처리합니다.

다음은 코드입니다.

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

class Main{
    static int N;
    static ArrayList<Integer> peoples = new ArrayList<>();
    static BufferedReader br;

    public static void main(String[] args) throws Exception{
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        long res = 0;
        Stack<People> stack = new Stack<>();

        for(int i=0;i<N;i++){
            int curr = Integer.parseInt(br.readLine());
            People next = new People(curr, 1);

            while(!stack.isEmpty() && stack.peek().height <= curr){
                People p = stack.pop();
                res += p.cnt;
                if(p.height == curr) next.cnt += p.cnt;
            }

            if(!stack.isEmpty()) res++;
            stack.push(next);
        }
        System.out.println(res);
    }
    static class People{
        int height;
        int cnt;

        People(int height, int cnt){
            this.height = height;
            this.cnt = cnt;
        }
    }
}