백준 17298번: 오큰수

문제

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

17298번: 오큰수

 

---

풀이

크기가 N인 수열 A = A1, A2,..., AN이 있을 때 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수인 Ai의 오큰수를 구하는 문제입니다.

---

코드

C언어

정수 배열 arr를 동적할당하여 입력받고 i를 포함한 for문에 들어갑니다. 이때 스택에는 배열의 인덱스 값이 들어갑니다.

for문 안에있는 while문 안에서 스택이 비어있지 않을 때 arr[i]가 arr[스택의 최상단 데이터(인덱스)]보다 클 때까지 arr[pop한 인덱스]을 arr[i]로 바꿔줍니다. (이때 새로운 정수 배열을 만들지 않은 이유는 어차피 이미 지나간 인덱스는 다시 확인하지 않기 때문입니다.) while문이 끝나면 i를 스택에 push합니다.

for문이 끝났을 때 arr[스택에 남아있는 데이터들]는 오른쪽에 자신보다 큰 수가 없다는 것을 의미하므로 모두 -1을 넣어줍니다.

이것만으로는 설명이 어렵기 때문에 { 3, 5, 2, 7 }이라는 수열로 예시를 들어 설명하겠습니다.

i = 0) 처음에 스택은 비어있기 때문에 0을 push합니다.

i = 1) arr[스택의 최상단 데이터(0)](3)이 arr[1](5)보다 작기 때문에 arr[pop한 데이터] = arr[0] = arr[1] = 5가 되고 1을 push합니다.

i = 2) arr[스택의 최상단 데이터(1)](5)이 arr[2](2)보다 작지 않기 때문에 while문을 빠져나오고 2를 push합니다.

i = 3) arr[스택의 최상단 데이터(2)](2)이 arr[3](7)보다 작기 때문에 arr[pop한 데이터] = arr[2] = arr[3] = 7가 되고 그 다음  arr[스택의 최상단 데이터(1)](5)이 arr[3](7)보다 작기 때문에 arr[pop한 데이터] = arr[1] = arr[3] = 7이 되고 3을 push합니다.

for문이 종료되었고 arr[스택에 남아있는 데이터(3)]의 오른쪽에는 자신보다 큰 수가 존재하지 않기 때문에 arr[pop한 데이터] = arr[3] = -1이 됩니다.

#include <stdio.h>
#include <stdlib.h>
int stack[1000000];
int idx = -1;
void push(int value) {
	stack[++idx] = value;
}
int pop() {
	return stack[idx--];
}
int is_empty() {
	return (idx == -1);
}
int peek() {
	return stack[idx];
}
main() {
	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < n; i++) {
		while (!is_empty() && arr[peek()] < arr[i]) {
			arr[pop()] = arr[i];
		}
		push(i);
	}
	while (!is_empty()) {
		arr[pop()] = -1;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}

자바

위의 C언어를 이용한 풀이와 동일하지만 스택을 따로 구현하지는 않고 자바 util 패키지의 Stack 클래스를 이용하였습니다. 또한 Stringbuilder를 이용하여 한꺼번에 출력하였습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
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));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<Integer>();
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        while (!stack.empty()) {
            arr[stack.pop()] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb);
    }
}

 

---

결론

처음에 이 문제를 봤을 때 여러 개의 for문을 사용하려고 했습니다. 그러다 보니 실행시간이 너무 오래 걸리게 되었고 시간 초과를 받았습니다. 그래서 문제를 차근차근 다시 읽어보고 스택이 필요하다는 것을 알게 되었고 이를 응용하여 문제를 풀었습니다. 스택에 들어갈 수 있는 데이터는 어떤 값이 아니라 배열의 인덱스 등 다양한 데이터가 될 수 있다는 것을 알게 되었습니다.