[백준] 17298번 오큰수 / C++ Java

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

C++

#include<iostream>
#include<stack>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int arr[1000000];
    int result[1000000];
    stack<int> s;
    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }


    for(int j = n-1; j >= 0; j--) {
        while(!s.empty()) {
            if(s.top() > arr[j]) {
                result[j] = s.top();
                break;
            }
            else{
                s.pop();
            }
        }
        if(s.empty()) {
            result[j] = -1;
        }
        s.push(arr[j]);
    }

    for(int k = 0; k < n; k++) {
        cout << result[k] << " ";
    }
}

Java

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

public class Main {
    public static void main(String[] args) throws Exception {
        // BufferedReader(new InputStreamReader(System.in))은 Scanneer와 동일
        // BufferedWriter(new OutputStreamWriter(System.out))은 System.out.print와 동일

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr1 = new int[1000000];
        int[] arr2 = new int[1000000];
        Stack<Integer> s = new Stack<>();
        // C++ stack<int> s; , Java Stack<Integer> s = new Stack<>();

        String[] input = br.readLine().split(" ");
        // 입력된 숫자들을 공백으로 구분하여 읽는다.

        for(int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(input[i]);
        }
        // parseInt는 String타입의 숫자를 int타입으로 변경

        for(int j = n-1; j >= 0; j--) {
            while(!s.isEmpty()) {
                if(s.peek() > arr1[j]) { // C++ s.top , Java s.peek()
                    arr2[j] = s.peek();
                    break;
                }
                else{
                    s.pop();
                }
            }
            if(s.isEmpty()) {
                arr2[j] = -1;
            }
            s.push(arr1[j]);
        }

        for(int k = 0; k < n; k++) {
            bw.write(arr2[k] + " ");
        }
        bw.flush();
        br.close();
    }
}

문제풀이

• 이중 for문을 사용해서 풀려고 했지만, 시간복잡도가 O(N^2)이라서 불가능했다. 따라서 스택을 사용해 <- 순서로 비교했다. s가 emtpy까지 while문을 돌리면서, s.top() > arr[j]일 때는 그 top값이 오큰수이기 때문에 top값을 result[j]에 넣는다. 아닌 경우에는 pop을 해주면서 오큰수를 찾는다. 그리고 while문을 빠져나왔을 때, s가 비어있으면 result[j]의 오큰수는 -1이다. 그 다음 s에 arr[j] 값을 push해준다.

Comment

• 골드 문제는 처음이었는데, 확실히 실버 문제와 난이도 차이가 있는 것 같다. 어려웠다...