크기가 N인 수열 A = A1, A1, ... , AN이 있다. 수열의 각 원소 Ai에 관련된 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 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(4) = -1 이다.
입력
1번째 줄에 수열 A의 크기 N(1 ⪯ N ⪯ 1,000,000), 2번째 줄에 수열 A의 원소 A1, A1, ... , AN(1 ⪯ Ai ⪯ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
예제 입력
4 // 수열의 크기
3 5 2 7
예제 출력
5 7 7 -1
1단계 - 문제 분석하기
N의 최대 크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다. 스택에 다음 아이디어를 추가해 이 문제를 풀자.
핵심 아이디어
• 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.
• 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다.
2단계 - 손으로 풀어 보기
문제 푸는 순서
- 스택이 채워져 있거나 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장한다. pop은 조건을 만족하는 동안 계속 반복한다. 과정 1을 마치면 과정 2로 넘어간다.
- 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어간다.
- 과정 1~2를 수열의 길이만큼 반복한 다음 현재 스택에 남아 있는 인덱스에 -1을 저장한다.
처음에는 스택이 비어 있으므로 과정1 없이 과정2를 진행. 인덱스 0을 push하고 다음 인덱스로 넘어간다.
인덱스 A[1]은 5이고 A[top]은 0이므로 스택에서 pop을 수행하고 Result[0]에 오큰수 5를 저장. 1회 반복으로 스택이 비었으므로 pop은 더 진행하지 않는다.
인덱스 1을 push하고 다음 인덱스로 넘어간다.
A[2]는 2이고 A[top]은 5이므로 과정2를 진행하여 push하고 다음 인덱스로 넘어간다.
A[3]은 7이고 A[top]은 2이므로 스택에서 pop을 수행하고 Result[2]에 오큰수 7을 저장. 스택이 남았으므로 과정1을 반복한다.
A[3]은 7이고 A[top]은 5이므로 스택에서 pop을 수행하고 Result[1]에 오큰수 7을 저장.스택이 비었으므로 pop은 더 진행하지 않는다.
인덱스 3을 push한다.
다음 인덱스가 없으므로 3을 pop하여 Result[3]에 -1을 저장한다.
3단계 - sudo코드 작성하기
N(수열 개수) A[](수열 배열) ans[](정답 배열)
수열 배열 채우기
최초 스택 초기화하기
for(N만큼 반복) {
while(스택이 비어 있지 않고, 현재 수열 값이 top에 해당하는 수열보다 크다면) {
pop()
정답 배열에 오큰수를 현재 수열로 저장하기
}
현재 수열을 스택에 push()
}
while(스택이 빌 때까지) {
스택에 있는 인덱스의 정답 배열에 -1 저장하기
}
정답 배열 출력하기4단계 - 코드 구현하기
import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class Q12 {
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int []A = new int[N];
int []ans = new int[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
for(int i = 0; i < N; i++){
A[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> myStack = new Stack<>();
myStack.push(0);
for(int i = 1; i < N; i++){
while(!myStack.empty() && A[myStack.peek()] < A[i]){
ans[myStack.pop()] = A[i];
}
myStack.push(i);
}
while(!myStack.empty()){
ans[myStack.pop()] = -1;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i = 0; i < N; i++){
bw.write(ans[i] + " ");
}
bw.write("\n");
bw.flush();
bw.close();
bf.close();
}
}
- Do it! 알고리즘 코딩테스트 자바 편
