백준 17298: 오큰수(java)

문제

---

풀이

 

수열을 저장할 배열 A[]와 스택 stack을 사용하고, 이때 stack의 원소로는 배열의 원소가 아닌 인덱스가 들어간다.

 

for문을 순회하며 A[stack.peek()]과 A[i]을 비교하고, A[stack.peek()] < A[i]이면서 스택이 공백 상태가 아닐 경우 스택이 빌 때까지 A[stack.peek()]과 A[i]를 비교하는 과정을 반복한다.  A[i]가 A[stack.peek()]의 오큰수이므로 배열을 업데이트한다.

 

자세한 내용은 예제 1을 풀이하며 설명하겠다.

 

i = 0

스택이 비어 있으므로 스택에 첫 번째 인덱스를 push한 후 시작한다.

0

 

 

i = 1

stack.isEmpty() = false이므로 A[stack.peek()]과 A[i]을 비교한다.

 

A[0] (=3) < A[1] (=5)라면 A[1]이 A[0]의 오큰수이므로 A[0] = A[1]로 업데이트하고, 스택에서 0을 pop한 후 스택에 i = 1을 push한다. 현재 stack = { 1 }이고, A = { 5, 5, 2, 7 }이다.

1

 

 

i = 2

stack.isEmpty() = false이므로 A[stack.peek()]과 A[i]을 비교한다.

 

A[1] (=5) < A[2] (=2)가 아니므로 스택에 i = 2를 push한다. 여전히 A = { 5, 5, 2, 7 }이며 stack = { 1, 2 }이다.

1

2

 

 

i = 3

stack.isEmpty() = false이므로 A[stack.peek()]과 A[i]을 비교한다.

 

A[2] (=2) < A[3] (=7) 이므로 스택에 A[2] = A[3]으로 업데이트하고, 스택의 최상단 값인 2를 pop한다. 현재 A = { 5, 5, 7, 7 } stack = { 1 }이다.

1

 

아직 스택에 요소가 남아 있으므로 A[stack.peek()] < A[i] 인지 판단하고, A[1] (=5) < A[3] (=7)이 성립함에서 A[1]의 오큰수 또한 A[3]임을 알 수 있으므로 A[stack.pop() (=1)] = A[3]으로 업데이트한 후 스택에 i = 3을 push한다. 이제 A = { 5, 7, 7, 7 }이고 stack = { 3 }이다.

3

 

for 루프가 종료된 시점에서 스택에는 오큰수를 가지지 못한 A[] 원소의 인덱스가, A[] 배열에는 A[i]의 오큰수가 저장되게 된다. while문을 돌며 스택에 남아 있는 값들을 전부 pop한 뒤, A[stack.pop()] = -1으로 업데이트한다.

 

위 알고리즘을 코드로 나타내면 아래와 같다.

for(int i=0; i<N; i++) {
	while(!stack.isEmpty() && A[stack.peek()]<A[i]) {
		A[stack.pop()]=A[i];
	}
	stack.push(i);
}
		
while(!stack.isEmpty()) {
	A[stack.pop()]=-1;
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		
		int N=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int[] A=new int[N];
		
		for(int i=0; i<N; i++) {
			A[i]=Integer.parseInt(st.nextToken());
		}
		
		Stack<Integer> stack=new Stack<>();	//인덱스가 들어감
		
		for(int i=0; i<N; i++) {
			while(!stack.isEmpty() && A[stack.peek()]<A[i]) {
				A[stack.pop()]=A[i];
			}
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			A[stack.pop()]=-1;
		}
		
		for(int i=0; i<N; i++) {
			sb.append(A[i]+" ");
		}
		
		System.out.println(sb);
	}
}