https://www.acmicpc.net/problem/3015
모노톤 스택
모노톤 스택은 스택의 요소가 오름차순 또는 내림차순으로 유지되도록 설계된 특수한 스택입니다. 이는 특정 조건을 만족하는 요소를 효율적으로 처리하거나 빠르게 접근해야 할 때 사용됩니다.
- 오름차순 스택: 스택에 쌓인 값이 항상 작아지지 않도록 유지.
- 내림차순 스택: 스택에 쌓인 값이 항상 커지지 않도록 유지.
모노톤 스택은 일반적으로 배열이나 리스트의 각 요소와 관련된 "가장 가까운 큰 값" 또는 "가장 가까운 작은 값"을 찾는 문제에 사용됩니다. O(N)의 시간 복잡도로 해결할 수 있어 효율적입니다.
문제 접근
이 문제 또한 모노톤 스택을 사용하여 해결할 수 있습니다.
먼저 서로를 볼 수 있는 조건을 생각해 봅시다.
- 두 사람이 서로 볼 수 있으려면 두 사람 사이에 둘 중 더 큰 사람보다 키가 큰 사람이 없어야 합니다.
- 따라서, 각 사람은 자신보다 키가 작은 사람들만 볼 수 있습니다.
여기서 우리는 스택을 현재까지 처리된 사람들의 키를 저장하고, 내림차순으로 정렬할 것입니다.
새로운 사람이 들어오면, 키가 작거나 같은 사람들을 처리하고 스택에서 제거합니다.
예를 들어 2 4 1 2 2 5 1 의 경우 처리 과정은,
- 첫 번째 사람(2): 스택에 추가 → 스택 상태: [2(1명)]
- 두 번째 사람(4): 스택 비움, 1명 볼 수 있음 → 스택 상태: [4(1명)]
- 세 번째 사람(1): 스택에 추가 → 스택 상태: [4(1명), 1(1명)]
- 네 번째 사람(2): 스택 비움, 1명 볼 수 있음 → 스택 상태: [4(1명), 2(1명)]
- 다섯 번째 사람(2): 같은 키 누적 → 스택 상태: [4(1명), 2(2명)]
- 여섯 번째 사람(5): 스택 비움, 3명 볼 수 있음 → 스택 상태: [5(1명)]
- 일곱 번째 사람(1): 스택에 추가 → 스택 상태: [5(1명), 1(1명)]
따라서 최종 출력은 10입니다.
특히 같은 키의 사람을 누적해야 합니다.
이를 위해 아래 Node 클래스를 정의합니다.
static class Node {
int height; // 사람의 키
long count; // 해당 키를 가진 사람의 수
public Node(int height, long count) {
this.height = height;
this.count = count;
}
}
사람의 키에 따른 count 값을 누적시키는 이유는 누적하지 않으면 같은 키를 가진 사람들 간의 쌍이나 새로운 사람과의 쌍을 제대로 계산하지 못해 정답이 틀리게 됩니다.
스택 처리 코드는 다음과 같습니다.
long count = 1;
// 스택에서 현재 키보다 작거나 같은 키를 처리
while (!stack.isEmpty() && stack.peek().height <= currentHeight) {
Node node = stack.pop();
answer += node.count; // 스택의 사람들은 현재 사람과 서로 볼 수 있음
if (node.height == currentHeight) {
count += node.count; // 같은 키의 사람 수를 누적
}
if (!stack.isEmpty()) answer += 1; // 스택이 비어있지 않으면 가장 큰 키인 사람과 쌍이므로 + 1
stack.push(new Node(current, count));
}
- 새 키가 들어오면, 스택의 맨 위에 있는 사람들과 비교:
- 새 키보다 작거나 같은 키들은 새 키와 볼 수 있는 관계를 형성합니다.
- 키가 같다면, 같은 키를 가진 사람들의 개수를 누적 처리합니다.
- 새 키보다 큰 키가 나오면:
- 새 키는 스택에 추가되며, 다음 비교를 위해 유지됩니다.
- 스택이 비어 있지 않으면:
- 새 키는 스택 맨 위 사람과도 볼 수 있습니다.
위 로직을 모든 요소들에 대해 수행하면 됩니다.
참고로, 정답 값의 타입은 Long 이어야 합니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Node {
int height;
long count;
public Node(int height, long count) {
this.height = height;
this.count = count;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Stack<Node> stack = new Stack<>();
long answer = 0;
for (int current : arr) {
long count = 1;
while (!stack.isEmpty() && stack.peek().height <= current) {
Node prev = stack.pop();
answer += prev.count;
if (prev.height == current) count += prev.count;
}
if (!stack.isEmpty()) answer += 1;
stack.push(new Node(current, count));
}
System.out.println(answer);
}
}
'Development > PS' 카테고리의 다른 글
[PS] 백준 도전 숫자왕 java 풀이 (비트마스킹으로 모든 경우의 수 찾기) (0) | 2024.11.26 |
---|---|
[PS] 코드트리 나무 타이쿤 java 풀이 (0) | 2024.11.25 |
[PS][PCCP 기출문제] 3번 / 충돌위험 찾기 java 풀이 (+조건문 없음, 64 lines) (1) | 2024.11.02 |
[PS] 백준 1107 리모컨 java 풀이 (0) | 2024.10.31 |
[PS] 프로그래머스 [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 java 풀이 (14번에서 틀린 이유) (0) | 2024.10.16 |