Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

18. 스택

스택을 구현하고 사용해 봅시다.

Java / Python

6. 오큰수

17298번

스택으로 풀 수 있는 꽤 어려운 문제

이번 문제는 크기가 N인 수열에서 각 원소에 대해 오른쪽에 있으면서 해당 원소보다 큰 수 중에서 가장 왼쪽 수를 구하는 문제입니다.
수열을 탐색할 때, 현재 원소가 이전에 있는 원소보다 작을 때 까지 수열의 index를 stack에 추가(push) 하는 것입니다. 만약 현재 원소가 스택의 top 원소를 인덱스로 하는 수열의 원소보다 클 경우 stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주는 원리입니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Stack;
 
public class Main {
 
	public static void main(String[] args) throws IOException {	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<Integer>();
        
		int N = Integer.parseInt(br.readLine());
		int[] seq = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
 
		for(int i = 0; i < N; i++) {			
			// 스택이 비어있지 않고
			// 현재 원소 > 스택의 맨 위 원소가 가리키는 원소 
			// 조건을 만족할 때 까지 stack의 원소를 pop
			// 해당 인덱스의 값을 현재 원소로 변환

			while(!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
				seq[stack.pop()] = seq[i];
			}			
			stack.push(i);
		}
		
		// 스택의 모든 원소를 pop하면서 해당 인덱스의 value = -1로
		while(!stack.isEmpty()) {
			seq[stack.pop()] = -1;
		}		
		StringBuilder sb = new StringBuilder();
        
		for(int i = 0; i < N; i++) {
			sb.append(seq[i]).append(' ');
		}	
		System.out.println(sb);
	}
}

• Python

import sys 
N = int(sys.stdin.readline()) 
seq = list(map(int, sys.stdin.readline().split())) 
stack = [] 
result = [-1 for _ in range(N)] 
stack.append(0) 
i = 1 
while stack and i < N: 
    while stack and seq[stack[-1]] < seq[i]: 
        result[stack[-1]] = seq[i] 
        stack.pop() 
    stack.append(i) 
    i += 1 
    
for i in range(N): 
    print(result[i], end = " ")