[java] 백준 - 17298 오큰수 -java

자료구조 공부 중 괜찮은 문제가 있어 작성! 

 

 

자료구조 공부 중

관련된 문제를 백준에서 찾아 풀다가 어려웠지만 재밌고 괜찮은 문제를 가져와봤다.

 

 

문제

---

크기가 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)을 공백으로 구분해 출력한다.

 

 

예제 입력

---

 

 

풀이

---

 

문제를 읽고도 한참을 이해를 못했다.

이게 뭔소리지.. 했다..

 

한참을 보니 패턴이 보였다.

현재 값보다 뒤에 있고 크기가 크고 최대한 왼쪽에 있는 수를 구하는 것.

 

예를 들자면 3 5 2 7 이렇게 입력을 받았으면

 

3 뒤에 있는 5 2 7 중에 3보다 크고 제일 왼쪽의수 = 5

 

5 보다 뒤에있고 5보다 크고 제일 왼쪽의 수 = 7

 

2 보다 뒤에있고 2보다 크고 제일왼쪽의 수 = 7 

 

7보다 뒤에 있는게 없음 = -1

 

그래서 결과 5 7 7 -1

 

 

틀린 코드 (시간 초과)

---

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

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 0; i < n; i++) {
			int index = Integer.MAX_VALUE;
			for (int j = i+1; j < n; j++) {
				if(arr[i] < arr[j]) {
					index = j;
					break;
				}
			}
			if(!(index == Integer.MAX_VALUE)) {
				arr[i] = arr[index];
			}else {
				arr[i] = -1;
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int value : arr) {
			sb.append(value + " ");
		}
		System.out.println(sb);
	}
}

 

현재 값보다 크고 제일 가까운 순서를 index에 담고 값을 바꾸는 작업을

2중 for문을 통해 진행하였다. 아무래도 2중 for문이라 입력 크기마다 시간복잡도가 올라가기 때문에 break문을 이용하여 시간을 단축시켜 보았지만 

37%에서 시간초과 ..

 

 

정답 코드

---

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

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		Stack<Integer> stack = new Stack<Integer>();
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 0; i < n; i++) {
			while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
				arr[stack.pop()] = arr[i];
			}
			stack.push(i);
		}
		while(!stack.isEmpty()) {
			arr[stack.pop()] = -1;
		}
		StringBuilder sb = new StringBuilder();
		for(int value : arr) {
			sb.append(value + " ");
		}
		System.out.println(sb);
	}
}

 

시간복잡도가 낮은(?) 스택을 이용해서 풀이 

스택에 인덱스를 넣어서 비교하는 방식으로 접근

 

 

정답!

 

 

 

더 상위 문제

오등큰수 

https://www.acmicpc.net/problem/17299

17299번: 오등큰수