[BOJ_17298/JAVA] 오큰수

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

17298번: 오큰수

문제

 

풀이

처음에는 뒤에 처음 나오는 큰수로 그냥 출력하기만 하면 된다고 생각했다. 하지만 구현하다보니 시간초과가 날 것 같아 방법을 바꿨다.

(그리고 풀리지도 않음 ㅋ)

 

방법을 찾아보니 stack을 이용해서 다들 풀었더라?... 이걸 어떻게 스택으로 풀지?

아직도 문제를 보고 이걸 스택으로 풀어야겠다는 감이 안잡혀 ㅠㅠ

그래도 사람들이 푼 방법을 보고 최대한 이해하고 다시 내가 짜서 해보았다....

 

스택에 가장 윗부분(peek)과 배열의 원소를 비교해서 배열의 원소가 크면, pop을 한 인덱스 값을 큰 배열의 원소로 바꿔주면 된다.

이게 무슨 소리냐...면

 

arr = {3,5,2,7}

1. 맨 처음에 3을 그냥 push. 이때 3의 인덱스는 0이니까 0을 push한다. (이유는 나중에 나옴)

2. 그 다음 원소인 5와 stack.peek()을 해서 비교했을 때 5가 더 크니까 pop하고 5의 인덱스인 1을 넣음.

그리고 pop한 인덱스(0)을 5로 바꾼다. (arr[0] = 5)

3. 5(peek)와 2를 비교했을 때 2가 작으니까 push를 한다. 이때도 2의 인덱스(2)를 push한다.

4. 7이랑 2(peek)와 비교했을 때 7이 더 크니까 2를 pop하고 arr[2]=7로 값 바꿈. 

이것을 while문으로 7보다 작은 값들을 반복함. 

5. 배열을 다 탐색하고 스택에 값이 남아있으면 큰 수가 없다는 의미이므로 -1 출력

6. 최종적으로 arr={5,7,7,-1} 이 된다.

 

여기서 핵심은 배열의 값이 아닌 index를 스택에 넣는다는 것이다.

그 이유는 배열의 Index값을 알아야 배열의 원소를 바꿔줄 수 있기때문이다.

 만약, 배열의 값을 저장했다면 배열의 값과 일치하는 인덱스를 찾아 다 뒤져 바꿔줘야하기때문에 시간을 절약할 수 있다.

 

코드

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

public class BOJ17298 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		Stack<Integer> stack = new Stack<>();
		
		int num = Integer.parseInt(br.readLine());
		int [] arr = new int[num];
		
		st = new StringTokenizer(br.readLine());
		
		int j=0;
		
		while(st.hasMoreTokens()) {
			arr[j]=Integer.parseInt(st.nextToken());
			j++;
		}

		stack.push(0);
		
		for(int i = 1; i < num; i++) {
			
			
			if(stack.isEmpty()) {
				stack.push(i);
			}
			
			while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
				arr[stack.pop()] = arr[i];
			}
			
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			arr[stack.pop()] = -1;
		}
		
		for(int i = 0; i < num; i++) {
			sb.append(arr[i]).append(' ');
		}
		
		System.out.println(sb);

	}

}

 

---

이번 문제는 골드 4 문제여서 어려웠다 ... ㅠ

이해는 했지만 이걸 어떻게 풀지...? 라는 의문만 가득...