[백준] 17298 오큰수 -Java / Python

 

 

 

그냥 읽고 손 가는대로 풀면 시간초과로 오답이 된다.

빠르게 처리할 수 있는 방법을 생각해 보자.

 

스택을 잘 활용하면 빠르게 처리할 수 있다.

일단 수를 담는 스택과 인덱스를 저장하는 스택을 만들자.

 

입력값을 배열에 넣어준 후에 차례대로 값을 검사한다.

 

값을 검사하면서 현재 검사하고 있는 값이 이전의 값보다 작으면 스택에 인덱스와 값을 넣어 준다.

만약 현재 검사하고 있는 값이 스택의 가장 윗부분의 값보다 크면 스택에서 값을 뺀다. 이 작업을 스택의 가장 윗부분의 값이 더 커질 때 까지 반복한다.

 

위의 작업이 끝나면, 마지막 처리로 스택에 남아있는 인덱스를 -1로 채워준다.

 

스택을 이렇게 활용하는 방법도 있다.. 기억해두자.

 

 

 

Java

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		Stack<Integer> stack = new Stack<>();
		Stack<Integer> stackidx = new Stack<>();

		int[] arr = new int[N];
		int[] ans = new int[N];

		for(int i=0; i<N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
	
		for(int i=0; i< N; i++){
			while(stack.size()>0 && stack.peek() < arr[i]){
				ans[stackidx.peek()] = arr[i];
				stack.pop();
				stackidx.pop();
			}
			stack.push(arr[i]);
			stackidx.push(i);
		}

		while(stackidx.size()>0){
			ans[stackidx.peek()] = -1;
			stackidx.pop();
		}

		ans[N-1] = -1;

		for(int i=0; i<N; i++){
			sb.append(ans[i]).append(" ");
		}

		

		System.out.print(sb);
	}

	
}

 

 

Python

 

 

파이썬도 자바와 같은 방법으로 풀었다.

 

from collections import deque
import sys

N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split(" ")))
ans = [-1] * N

st = []
stidx = []

for i in range(N):
  while st and st[-1] < arr[i]:
    ans[stidx[-1]] = arr[i]
    st.pop()
    stidx.pop()
  st.append(arr[i])
  stidx.append(i)

while stidx:
  ans[stidx[-1]] = -1
  stidx.pop()

ans[N-1] = -1

for i in ans:
  print(i, end=" ")