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

1. 문제 요약

한 줄로 서 있는 사람들 중에서 서로 볼 수 있는 쌍의 개수를 구하는 문제이다.

→ 두 사람이 서로 볼 수 있으려면 사이에 있는 사람들 중에서 둘 중 하나보다 더 큰 사람이 없어야 한다.

---

2. 처음 접근 (실패한 방식)

처음에는 이렇게 생각했다.

각 사람 i 기준으로 오른쪽을 보자

- 계속 비교하면서
- 처음 나보다 큰 사람을 만나면 상태 전환
- 이후 감소하면 종료

 

즉, 흐름을 이렇게 단순화했다.

• V 형태는 가능
• ^ 형태는 불가능

그래서 아래처럼 구현했다.

for i in range(n):
    check = False
    for j in range(i+1, n):
        if not check:
            answer += 1
            if heights[i] < heights[j]:
                check = True
        else:
            if heights[i] > heights[j]:
                break
            answer += 1

---

3. 문제점 분석

결과가 10이 아니라 13이 나옴 → 오답

왜 틀렸을까?

“처음 나보다 큰 사람을 만난 이후의 처리 방식이 틀렸다”

---

4. 반례로 이해하기

2 4 1

 

• 2 → 4는 보임
• 2 → 1은 안 보임

왜냐하면
→ 사이에 있는 4가 1보다 크기 때문

---

5. 내가 놓친 핵심

나는 이렇게 생각했었다.

"한 번 큰 사람 만나면 그 뒤는 계속 볼 수 있지 않을까?"

근데 실제 조건은

→ 중간에 있는 모든 사람을 계속 체크해야 한다

즉,

• 단순히 "한 번 큰 사람 만났는지"
• "증가/감소 흐름인지"

이게 아니라

→ 사이에 있는 최대값이 계속 영향을 줌

---

6. 핵심 아이디어: 단조 스택

이 문제는 단조 감소 스택으로 해결해야 한다.

스택이 의미하는 것

스택에는 현재 사람과 관계가 아직 끝나지 않은 후보들이 들어있다.

---

 해결 전략

새로운 사람 h가 들어올 때:

 1) 나보다 작은 사람들 제거

 

while stack and stack[-1][0] < h:
answer += stack[-1][1]
stack.pop()

 

→ 작은 사람들은 이제 관계가 확정됨 (서로 볼 수 있음)

---

 2) 같은 키 처리

 

if stack and stack[-1][0] == h:

 

→ 같은 키는 서로 전부 볼 수 있음
→ 묶어서 개수 관리

---

 3) 더 큰 사람이 남아 있다면

 

if stack:
answer += 1

 

→ 바로 앞의 큰 사람은 항상 볼 수 있음

---

7. 최종 코드

 

import sys
input = sys.stdin.readline

n = int(input())
answer = 0
stack = []

for _ in range(n):
    h = int(input())
    cnt = 1

    while stack and stack[-1][0] < h:
        answer += stack.pop()[1]
    
    if stack and stack[-1][0] == h:
        same_cnt = stack.pop()[1]
        answer += same_cnt
        if stack:
            answer += 1

        stack.append((h, same_cnt + 1))
    else:
        if stack:
            answer += 1
        stack.append((h, 1))

print(answer)

 

---

8. 시간복잡도

• 각 원소는 최대 한 번 push / pop
  → O(N)

→ N = 500,000에서도 안전