오큰수

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

17298번: 오큰수

 

 

소스코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Stack<Node> s = new Stack<>();

        int arr[] = new int[n];
        for (int i = 0; i < n; i++) arr[i] = -1;

        s.push(new Node(Integer.parseInt(st.nextToken()), 0));
        for (int i = 1; i < n; i++) {
            int c = Integer.parseInt(st.nextToken());
            if (s.peek().v >= c) {
                s.push(new Node(c, i));
            } else {
                while(true) {
                    Node pop = s.pop();
                    arr[pop.idx] = c;
                    if(s.isEmpty()) {s.push(new Node(c, i)); break;}
                    if(s.peek().v >= c) {s.push(new Node(c, i)); break;}
                }
            }
        }

        for (int i : arr) bw.write(i + " ");
        bw.flush();
    }
}
class Node {
    int v; int idx;
    public Node(int v, int idx) {
        this.v = v;
        this.idx = idx;
    }
}

 

 

해결방법

오큰수란? 오른쪽에 있으면서 나보다 큰 값을 의미한다.

내가 푼 방법은 입력받은 값이 스택에 있는 값보다 크다면 pop()을 하여 결과값 배열에 저장을 반복하였다. 이후 입력받은 값을 스택에 저장하였다. pop()을 하여 결과값 배열에 저장하는 과정에서 스택에서 반환된 값이 배열의 어느 위치에 들어가야하는지 알기 위해 Node객체를 만들어 해결하였다.

 

 

개선된 소스코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Stack<Integer> s = new Stack<>();

        int arr[] = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int ans[] = new int[n];
        for (int i = n-1; i >=0; i--) {
            while (!s.isEmpty() && s.peek() <= arr[i])
                s.pop();
            ans[i] = s.isEmpty() ? -1 : s.peek();
            s.push(arr[i]);
        }

        for (int an : ans) {
            bw.write(an + " ");
        }
        bw.flush();
    }
}

 

 

개선된 해결방법

입력받은 값들을 배열에 저장한 후 배열의 맨 뒤부터 조사를 한다.

스택이 비어있지 않고 peek()값보다 현재 값이 크거나 같다면 pop()을 한다.

이후 스택이 비어있다면 -1을 결과 배열에 저장하고 비어있지 않다면 peek()값을 결과 배열에 저장한다. 이때 -1과 peek()값은 오큰수이다. 마지막으로 입력받은 값을 스택에 저장한다. 이 과정을 반복한다.

내가 구현한 방법보다 훨씬 효율적인 것 같다.