백준 17298번 <오큰수>

백준 알고리즘 17298번

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

17298번: 오큰수

ㅎㅎ 처음 풀 때 이중 for문 돌려서 시간 초과 났다.

그리고서 구글링...

---

17298번

주어진 길이의 수열을 입력받아서 각 원소의 오른쪽에 있는 수들 중 각 원소보다 크고 제일 왼쪽에 있는 수를 찾아서 출력하는 문제이다.

 

처음에는 앞에서부터 수열을 봐서 뒤에 있는 수 중 큰 수를 찾으려고 했는데

그러려면 이중 for문을 돌리는 방법밖에 생각이 나지 않았다!!

 

구글링을 해보니까 stack을 이용하고 입력받은 수열을 뒤에서부터 봤다!!!!

---

문제 해결

input이라는 int형 배열에  입력받은 수열을 넣고

result라는 int형 배열을 만들어서 결과를 저장할 것이다.

stack을 만들어서 오큰수를 구할 것이다.

 

for문을 입력받은 수열의 크기(n)-1부터 0까지 돌린다.

1. stack이 비어있으면

result[i] = -1

2. stack이 비어있지 않으면

   1) stack의 top이 input[i]보다 크면  -> i번째 수보다 오른쪽에 있으면서

   가장 왼쪽에 있고 큰 수가 stack의 top

   result[i] = stack의 top

   2) stack의 top이 input[i]보다 작거나 같으면 -> 오큰수 아님!

      while문을 돌린다. stack의 top이 input[i]보다 크면 while문을 빠져나온다.

      while문 안에서는 stack의 top을 뺀다.

      -> stack의 top이 input[i]보다 작거나 같으니까 오큰수 아님

      만약 stack이 비었으면 break.

      while문을 빠져나와서 stack이 비었으면 result[i]=-1

      그렇지 않으면 result[i] = stack의 top

3. stack에 input[i]를 넣는다.

이때 input[i]를 stack에 넣어서 stack의 top이 되니까 input[i]보다 작은 거는 빼도 된다.

      

완젼 어렵다. 이해하는데 오래 걸렸다.. 구글링이 아니라면 생각할 수.. 있었을까..

---

코드

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));
		StringBuffer sb = new StringBuffer();
		
		int num = Integer.parseInt(br.readLine());

		int input[] = new int[num];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < num; i++) {
			int a = Integer.parseInt(st.nextToken());
			input[i] = a;
		}
		
		Stack<Integer> stack = new Stack<Integer>();
		
		int result[] = new int[num];
		
		for(int i = num-1; i >= 0; i--) {
			if(stack.isEmpty()) {
				result[i] = -1;
			}else {
				if(stack.peek() > input[i]) {
					result[i] = stack.peek();
				}else {
					while(stack.peek() <= input[i]) {
						stack.pop();
						if(stack.isEmpty()) {
							break;
						}
					}
					if(stack.isEmpty()) {
						result[i] = -1;
					}else {
						result[i] = stack.peek();
					}
				}
			}
			stack.push(input[i]);
		}
		
		for(int i = 0; i < num; i++) {
			sb.append(result[i] + " ");
		}
		System.out.println(sb.toString());
	}

}

---