이번에 풀어본 문제는
백준 3015번 오아시스 재결합 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

class Height
{
    int height,cnt;

    public Height(int height, int cnt) {
        this.height = height;
        this.cnt = cnt;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Stack<Height> s = new Stack<>();
        long answer = 0;
        for (int i = 0; i < N; ++i) {
            int cur = Integer.parseInt(br.readLine());
            Height next = new Height(cur, 1);
            while (!s.isEmpty() && s.peek().height <= cur) {
                Height p = s.pop();
                answer += p.cnt;
                if (p.height == cur) next.cnt += p.cnt;
            }

            if (!s.isEmpty()) answer++;
            s.push(next);
        }
        System.out.print(answer);
    }
}

📝 풀이

주어진 입력값은 키를 의미하고, 해당 순서로 줄을 서있다고 할 때, 자신보다 키가 큰 사람이 사이에 있다면 반대편과 마주볼 수 없습니다. 위와 같은 조건에서 서로가 마주 볼 수 있는 두 쌍의 총 수를 구하는 문제입니다.
반복은 입력 순서대로 진행됩니다. 만약 새로 들어온 입력값이 스택의 top보다 크다면, top은 더이상 그 뒤에 들어오는 사람들을 마주할 수 없다는 의미이므로 pop으로 꺼내주며 카운트를 더해줍니다. 만약 키가 같은 경우라면, cnt값을 누적합 시켜주고, 다시 집어넣어주면 됩니다. 자신보다 작은 키를 모두 제거한 이후에도 스택에 값이 남아있다면, 다 꺼낸상태에서의 top도 마주볼 수 있기 때문에 카운트를 1 증가시킬 수 있습니다.

📜 후기

개인적으로 스택을 활용하기가 생각보다 너무 어려운 것 같습니다.. 자주 풀어보지 않았던 유형이라는 생각이 들어서, 다음 문제도 스택 관련한 문제를 풀어봐야겠습니다,,