b3015. 오아시스 재결합

 

https://www.acmicpc.net/problem/3015

 

 

 

📌 자바(Java)로 푸는 오아시스 재결합 문제 풀이 🚀

---

🔎 문제 개요

이 문제는 백준 3015번 - 오아시스 재결합 문제입니다.
주어진 사람들의 키 정보를 기반으로 서로 볼 수 있는 쌍의 개수를 구하는 문제입니다.

---

💡 예제 입력

7
2
4
1
2
2
5
1

💡 예제 출력

10

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 스택(Stack) 을 활용한 O(N) 최적화 방법을 사용합니다.

✏️ 주요 고려 사항

✔ 각 사람의 키(h)를 기준으로 볼 수 있는 사람의 쌍을 계산해야 합니다.
✔ 스택을 활용하여 효율적으로 볼 수 있는 쌍을 계산할 수 있습니다.
✔ 스택에는 항상 오름차순으로 저장하여, 현재 키보다 작거나 같은 사람을 볼 수 있도록 합니다.
✔ 같은 키를 가진 사람들은 한 번에 처리하여 중복 계산을 줄입니다.

---

🔹 Java 코드 해설

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

public class Main {

    static class Node {
        int height;
        int count;

        public Node(int h, int cnt) {
            this.height = h;
            this.count = cnt;
        }
    }

    static int N;
    static Stack<Node> st;

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

        N = Integer.parseInt(br.readLine());
        st = new Stack<>();
        long answer = 0;

        for (int i = 0; i < N; i++) {
            int height = Integer.parseInt(br.readLine());
            int count = 1;

            // 스택의 최상단 값보다 작은 경우 볼 수 있는 쌍을 계산
            while (!st.isEmpty() && st.peek().height <= height) {
                Node top = st.pop();
                answer += top.count;

                if (top.height == height) {
                    count += top.count;
                }
            }

            // 스택이 비어 있지 않다면 추가로 1쌍을 형성할 수 있음
            if (!st.isEmpty()) {
                answer++;
            }

            st.push(new Node(height, count));
        }

        System.out.println(answer);
    }
}

---

🔍 코드 설명

📌 1. 스택 활용한 볼 수 있는 쌍 계산

static Stack<Node> st;

• 스택에는 {키, 같은 키의 개수} 정보를 저장합니다.
• 스택은 오름차순으로 유지되며, 낮아지는 경우 볼 수 있는 사람들을 계산하면서 pop()합니다.

---

📌 2. 현재 키보다 작은 키들은 스택에서 제거하며 볼 수 있는 쌍 계산

while (!st.isEmpty() && st.peek().height <= height) {
    Node top = st.pop();
    answer += top.count;

    if (top.height == height) {
        count += top.count;
    }
}

🔹 동작 방식

• 현재 키보다 작은 값들은 스택에서 제거하면서 카운트
• 제거된 키들은 현재 사람을 볼 수 있으므로 answer 에 추가
• 같은 키를 가진 경우 count를 증가시켜 한 번에 처리

---

📌 3. 스택이 비어 있지 않다면 추가 쌍 추가

if (!st.isEmpty()) {
    answer++;
}

• 스택이 비어 있지 않다면, 현재 사람은 이전 사람을 볼 수 있음
• 따라서 answer를 +1 증가

---

📌 4. 새로운 노드 추가

st.push(new Node(height, count));

• 현재 사람을 스택에 추가 (키와 함께, 같은 키 개수 저장)

---

🔥 시간 복잡도 분석

연산 최악의 경우 수행 횟수 시간 복잡도

for 루프	N	O(N)
while 루프 (스택에서 pop)	N	O(N)
총합		O(N)

✅ 모든 연산이 O(N) 이내로 수행되므로 매우 효율적입니다.

---

🏆 정리

✅ 핵심 포인트

✔ 스택을 활용하여 볼 수 있는 쌍을 효율적으로 계산
✔ 같은 키는 한 번에 처리하여 중복 계산 방지
✔ 시간 복잡도를 O(N)으로 최적화하여 빠르게 해결

---

🎯 이 알고리즘의 장점

✅ 스택을 활용한 O(N) 풀이로 효율적
✅ 볼 수 있는 쌍을 빠르게 탐색 가능
✅ 다른 "볼 수 있는 사람 쌍" 문제에서도 활용 가능