반응형
백준_17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
스택
참고 포스팅
[백준] 1874_스택 수열 - JAVA
백준_1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.
devhan.tistory.com
코드
import java.io.*;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(br.readLine());
int[] A = new int[n]; // 수열 생성
int[] answer = new int[n]; //정답 배열 생성
String[] str = br.readLine().split(" ");
for(int i = 0; i < n; i++) {
A[i] = Integer.valueOf(str[i]);
}
Stack<Integer> myStack = new Stack<>();
myStack.push(0);
for(int i = 1; i < n; i++) {
while(!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
answer[myStack.pop()] = A[i];
}
myStack.push(i);
}
while(!myStack.empty()) {
answer[myStack.pop()] = -1;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < n; i++) {
bw.write(answer[i] + " ");
}
bw.write("\n");
bw.flush();
}
}이 문제에서 핵심으로 생각할 포인트는 아래와 같다.
- 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.
- 오큰수를 구한 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력한다.
제출 결과
반응형