[백준 / BOJ] 17298 오큰수 (Java)

문제

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

17298번: 오큰수

N개의 수로 이루어진 수열이 있다.

이 수열의 i번째 원소를 Ni라 할때, Ni보다 오른쪽에 있으면서 Ni보다 큰 수를 찾아서 구하는 프로그램을 만드는 문제다.

---

풀이

스택으로 푸는 문제다.

 

수열에서 Ni보다 오른쪽에 있는 수중 더 큰수를 찾아야한다. 즉, 입력받는 Ni을 스택에 계속 집어넣으면서, Stack의 가장 위에있는 원소가 입력받은 Ni보다 더 큰 경우 스택의 가장 위에있는 원소가 Ni보다 클때까지 pop해준다.

 

위 과정을 반복하면, 알고리즘 수행중 스택은 감소수열 상태가 유지되고, 답을 최대 O(2N)만에 구할수있다.

 

* 이 문제의 경우 입출력시간을 신경써줘야한다. *

평소 자바로 문제를풀때, 입력은 BufferedReader, 출력은 기본 system.print문(어떠한 시간 줄임도 없이)을 사용했다. 이러한 방법으로 할경우 시간초과가 나온다.

시간을 줄이기위해서, StringBuffer로 답을 합친후, 한번에 System.out으로 출력해버렸다.

 

주요 소스코드

    private void operateStack(Node node){
        while(!stack.isEmpty() && (stack.peek().num < node.num)) ans[stack.pop().idx] = node.num;
        stack.add(node);
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/17299%20%EC%98%A4%ED%81%B0%EC%88%98/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃