Java 17298 오큰수

 

풀이 : 

오큰수란 자신의 오른쪽에 있는 자신보다 큰 수를 말한다. 예를 들어 3, 5, 2, 7 란 수열이 있을 때 3을 기준으로 5가 가장 가까운 큰수이기에 3의 오큰수는 5가 된다.

 

문제를 이해하고 시간제한을 확인하지 않고 이중for문을 사용하여 풀이하다가 시간초과가 나버렸다 ...

그래서 이중for문이 아닌 while문으로 스택을 활용하여 풀이하였다.

 

우선 주어진 수열을 for문으로 array에 초기화 해준 뒤 arr라는 int형 배열타입에 저장해주었다.

그리고 첫번째 원소는 무조건 비교대상이 되어야하니 stack에 0을 푸쉬해주었다.

for문을 첫번째 원소는 푸쉬해두었으니 1부터 arr.length까지 진행하고 그 안에 while문으로 stack이 비어있지 않고, 스택의 top이 arr[인덱스]보다 작다면 오큰수를 찾았으므로 pop을 하고 그 값을 arr[인덱스]에 저장하면 된다.

찾지 못한 경우에는 stack에 push, 반복문이 끝나면 stack에 남아있는 원소들은 오큰수를 찾지 못한 경우이니 arr[stack.pop()] = -1로 값을 저장하면 해결할 수 있었다.

 

말은 쉽지만 해결하는 과정에선 복잡해서 애를 먹었다.

 

 

통과한 코드 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        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());
        }
        for(int i = 0; i < n; i++){
            while(!s.isEmpty() && arr[s.peek()] < arr[i]){
                arr[s.pop()] = arr[i];
            }
            s.add(i);
        }
        while(!s.isEmpty()){
            arr[s.pop()] = -1;
        }
        for(int i = 0; i < arr.length; i++){
            sb.append(arr[i]).append(" ");
        }
        System.out.print(sb);
    }
}

 

 

시간 초과 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = 0; i < n; i++){
            Stack<Integer> s = new Stack<>();
            int num = arr[i];
            s.push(num);
            for(int j = i; j < n; j++){
                int k = arr[j];
                if(num < k){
                    s.push(k);
                    break;
                }
            }
            if(s.size() > 1){
                sb.append(s.pop()).append(" ");
            } else {
                sb.append(-1).append(" ");
            }
        }
        System.out.print(sb);
    }
}