[Baekjoon] 17298_오큰수

Gold IV

문제(출처: https://www.acmicpc.net/problem/17298)

---

< 오큰수 >

 

문제 풀이 & 생각

 

처음에는 이중 포문을 사용해서 구현했더니 시간초과가 발생했다.

 

stack을 사용하여 시간초과를 해결할 수 있었다.

현재 값과 다음 값을 비교하여 다음 값이 크다면 오큰수 이므로 답을 출력하고 오큰수가 아니라면 stack에 넣어 큰 값이 올 때까지 기다리는 방법으로 구현했다.

 

 

 my solution (Java)

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

public class _17298_ { // 오큰수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine());

		Stack<Integer> stack = new Stack<>();
		int arr[] = new int[n];
		int result[] = new int[n];
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
			result[i] = -1;
		}

		for (int i = 0; i < n - 1; i++) {
			if (arr[i] < arr[i + 1]) {
				result[i] = arr[i + 1];
				if (!stack.isEmpty()) {
					while (!stack.isEmpty()) {
						if (arr[stack.peek()] < arr[i + 1]) {
							int num = stack.pop();
							result[num] = arr[i + 1];
						}else {
							break;
						}
					}
				}

			} else {
				stack.add(i);
			}
		}
		for (int i = 0; i < n; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
	}
}

 

Main

- 수열 A의 크기 (n) 입력

- arr : 수열 저장

  result: 오큰수 저장

- 수열을 탐색하며 현재 값과 다음 값을 비교 -> 다음 값이 현재 값 보다 크다면 오큰수 이므로 result 배열에 저장, stack에 값이 있는지 확인 후 stack에 있는 값이 다음 값보다 작다면 stack에 있는 값의 오큰수를 찾은 것이므로 오큰수 저장  But 오큰수가 아니라면 오큰수를 찾기 위해 stack에 값을 저장

- result 배열 출력

 

---

---