View
https://www.acmicpc.net/problem/17298
📚 문제
Ai의 오큰수 NGE(i)는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다.
A = [9, 5, 4, 8]인 경우 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE($) = -1이다.
📝 문제 해결
입력받은 수들을 먼저 배열에 넣어주고 0번 인덱스부터 차례대로 값을 stack에 넣어준다.
stack이 비어있지 않으면서 새로 들어올 값이 해당 인덱스(stack 맨 위의 값)의 배열 값보다 크다면
stack의 맨 위 값을 pop하고 해당 인덱스의 배열값을 새로운 값으로 교체해준다.
input | stack | |
처음이라 스택이 비어있으므로 push 0 | {3, 5, 2, 7} | {0} |
스택이 비어있지 않고 input[0] < input[1]이므로 pop 0 그리고 input[0] = input[1] |
{5, 5, 2, 7} | {} |
push 1 | {5, 5, 2, 7} | {1} |
스택이 비어있지 않으나 input[1] > input[2]이므로 input 변화 없음 |
{5, 5, 2, 7} | {1} |
push 2 | {5, 5, 2, 7} | {1, 2} |
스택이 비어있지 않고 input[2] < input[3] 이므로 pop 2 그리고 input[2] = input[3] |
{5, 5, 7, 7} | {1} |
스택이 비어있지 않고 input[1] < input[3] 이므로 pop 1 그리고 input[1] = input[3] |
{5, 7, 7, 7} | {} |
push 3 | {5, 7, 7, 7} | {3} |
스택이 비어있지 않으므로 pop 3 그리고 input[3] = -1 | {5, 7, 7, -1} | {} |
💻 코드
package algorithm;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Stack;
public class BOJ17298 {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<Integer>();
int N = Integer.parseInt(br.readLine());
int[] input = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < N; i++) {
while(!stack.isEmpty() && input[stack.peek()] < input[i]) {
input[stack.pop()] = input[i];
}
stack.push(i);
}
while(!stack.isEmpty()) {
input[stack.pop()] = -1;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
sb.append(input[i]).append(' ');
}
System.out.println(sb);
}
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[최단 경로] 백준 11404번 플로이드(Java) (0) | 2022.10.24 |
---|---|
[스택] 백준 1874번 스택 수열(Java) (0) | 2022.10.19 |
[스택] 백준 4949번 균형잡힌 세상(Java) (1) | 2022.10.18 |
reply