[백준/자바] 17298 오큰수 구하기

[백준/자바] 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이다.

 

 

⚔ 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN(1 ≤ Ai ≤ 1,000,000)이 주어진다.

 

 

📣 출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

 

 

---

 

 

 

💎 문제분석하기

 

 

2중 반복문을 사용해 푼다면 쉬운 풀이가 될 수 있지만 N이 10^6이므로 시간 제한으로 통과하지 못할 것이다. 

 

스택을 활용해 풀어보자. 

 

스택은 후입선출을 특징으로 한다. 

 

 

입력으로 주어지는 수열과 

해당 수열에서 만들어지는 idx 수열을 별도로 생각해야 하는 것이 관건이다. 

 

각각의 스택을 만든다고 가정한다. 

 

아이디어는 스택에 수열의 숫자를 순서대로 넣을 때, idx를 넣어준다. idx를 통해 수열을 판단할 수 있기 때문에, 현재 들어온 인덱스로 확인되는 수열이 이전에 존재하는 인덱스로 확인되는 수열보다 크다면, 그 수가 오큰수이다. 

 

정답 배열의 그 오큰수 이전의 idx 자리에 위치하는 곳으로 해당 수열을 넣어준다. 

 

루프문을 돌면서 이를 반복하고, 루프문이 종료된 이후 스택에 존재하는 idx 값이 있다면, 곧 그 자리의 수열은 오큰수가 없음을 의미하므로, 해당 위치를 -로 채워준다. 

 

그림으로 그려가면서 생각해야 이해가 될 수 있다. 

 

 

 

 

 

 

💡 코드 구현하기

 

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		Stack<Integer> stack = new Stack<>();

		int N = sc.nextInt();
		int[] numbers = new int[N];

		for(int i = 0; i < N; i++) {
			numbers[i] = sc.nextInt();
		}

		for(int i = 0; i < N; i++) {
			// 스택이 비어 있으면 push를 한다 => 그렇지 않은 경우 반복문 형성
			// 스택의 맨 위 수로부터 판단되는 수열의 수가 현재 수보다 작다면 => 오큰수라면 => 바꿔준다
			while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
				numbers[stack.pop()] = numbers[i];
			}

			stack.push(i);
		}

		// 반복문이 끝났으므로 아직 idx 스택에 남아있는 요소를 가져와
		// 수열의 자리에 -1로 저장 = 초기화한다

		while(!stack.isEmpty()) {
			numbers[stack.pop()] = -1;
		}

		StringBuilder sbAnswer = new StringBuilder();
		for(int i = 0; i < N; i++) {
			sbAnswer.append(numbers[i]).append(' ');
		}

		System.out.println(sbAnswer);
	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편