[백준] 17298 오큰수

문제

---

크기가 N인 수열 A = A1, A2, ..., 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이다.

 

 

풀이

---

기본적으로 문제의 의도는 Stack을 사용하는 문제다.

 

Stack을 이용하여 푸는 방식은 아래와 같다.

 

1. 스택이 비어있으면 현재의 인덱스를 넣어준다.

2. 스택이 비어있지 않다면 현재 인덱스와 스택의 가장 나중에 들어온 인덱스의 값의 크기를 비교한다.

3. 현재의 값이 스택의 마지막 값보다 더 작다면 스택에 넣어준다. (if ( A[stack.peek()] > A[index] )-> stack.add(index)) 

4. 현재의 값이 스택의 마지막 값보다 크다면 작을 때까지 pop 하며 정답배열을 채워준다. if( A[stack.peek()] < A[index]) -> while(A[stack.peek()] > A[index] ) { answer[stack.pop()] = A[i] }

5. 마지막 값까지 확인한 뒤에도 Stack 에 남아있는 값들은 모두 -1 을 넣어주면 된다.

 

 

위의 순서를 코드로 표현하면 아래와 같다.

for(int i = 0 ; i < n ; i++) {			
	
	while(!stack.isEmpty()) {
		if(A[stack.peek()] < A[i]) {
			answer[stack.pop()] = A[i];
		}
		else {
			break;
		}
	}						
	
	stack.add(i);
}

 

 

<스택풀이 전체 코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int n;
	static int[] A;
	static int[] answer;
	
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));	
		
		n = parseInt(bufferedReader.readLine());
		A = new int[n];
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < n ; i++) {
			A[i] = parseInt(st.nextToken());
		}
		
		Stack<Integer> stack = new Stack<>();		
		answer = new int[n];		

		for(int i = 0 ; i < n ; i++) {			
			
			while(!stack.isEmpty()) {
				if(A[stack.peek()] < A[i]) {
					answer[stack.pop()] = A[i];
				}
				else {
					break;
				}
			}						
			
			stack.add(i);
		}
		
		while(!stack.isEmpty()) {
			answer[stack.pop()] = -1;
		}
		
		for(int i = 0 ; i < n ; i++) {
			sb.append(answer[i] + " ");
		}
		
		System.out.println(sb);		
	}	
}

 

이렇게 스택으로 푸는 방식이 있다.

 

 

나는 또다른 방식으로 풀었다.

뒤에서 부터 보면서 자신의 인덱스보다 가장 가까운 큰 값의 인덱스를 저장하는 방식이다.

 

9 5 4 8 을 예를 들면

 

1 2 3 4 를 저장을 미리 해둔 뒤

 

4보다 큰 가장 가까운 오큰수는 8이므로 세번째 배열의 위치에는 4를 저장한다.

1 2 4 4

 

5보다 큰 가장 가까운 오큰수는 8이므로 두번째 배열의 위치에는 4를 저장한다.

1 4 4 4

 

9보다 큰 가장 가까운 오큰수는 없으므로 아무것도 변경하지 않는다.

1 4 4 4

 

이렇게 저장된 배열에서 자신의 인덱스와 저장 된 오큰수 인덱스가 같은 값에 -1을 출력한다.

 

위와 같은 방식으로 문제를 구현하였고, 코드는 아래와 같다.

for(int i = n - 2 ; i >= 0 ; i--) {
	
	if(A[i] < A[i + 1]) {
		parent[i] = i + 1;
		continue;
	}
	
	int next = parent[i + 1];
	while(true) {
		if(A[i] < A[next]) {
			parent[i] = next;
			break;
		}
		
		if(parent[next] == next) {
			break;
		}
		
		next = parent[next];
	}			
}


for(int i = 0 ; i < n ; i++) {
	if(parent[i] == i) {
		sb.append("-1 ");
	}
	else {
		sb.append(A[parent[i]] + " ");
	}
}

종료 조건은 오큰수가 자기자신인 것이 나오면 반복문을 종료하게 하였다.

처음 탐색을 시작할 때는 자신의 바로 오른쪽 수부터 확인을 한다.

 

<가장 가까운 오큰수 인덱스를 저장하는 방식>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int n;
	static int[] A;
	static int[] answer;
	static int[] parent;
	
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));	
		
		n = parseInt(bufferedReader.readLine());
		A = new int[n];
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < n ; i++) {
			A[i] = parseInt(st.nextToken());
		}
		
		parent = new int[n];
		for(int i = 0 ; i < n ; i++) {
			parent[i] = i;
		}
		
		for(int i = n - 2 ; i >= 0 ; i--) {
			
			if(A[i] < A[i + 1]) {
				parent[i] = i + 1;
				continue;
			}
			
			int next = parent[i + 1];
			while(true) {
				if(A[i] < A[next]) {
					parent[i] = next;
					break;
				}
				
				if(parent[next] == next) {
					break;
				}
				
				next = parent[next];
			}			
		}
		
		
		for(int i = 0 ; i < n ; i++) {
			if(parent[i] == i) {
				sb.append("-1 ");
			}
			else {
				sb.append(A[parent[i]] + " ");
			}
		}
		
		System.out.println(sb);		
	}	
}