[스택] 17298 : 오큰수

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

17298번: 오큰수

똑똑하게 스택을 사용한다면 이런 방법인 것 같다.

스택문제 인덱스를 사용해서 풀이하는 방법 인지해두고 다른 문제에 적용시켜보자

참고한 블로그 - https://st-lab.tistory.com/196

 

내 코드

메모리 : 144348 KB

시간 : 980 ms

코드 길이 : 916 B

 

[내 코드]

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();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
		}
		
		Stack<Integer> stack = new Stack<>();
		
		for(int n = 0; n < N; n++) {
			while(!stack.isEmpty() && arr[stack.peek()] < arr[n])
				arr[stack.pop()] = arr[n];
			stack.push(n);
			}
		while(!stack.isEmpty()) {
			arr[stack.pop()] = -1;
		}
		
		for(int n = 0; n < N; n++) {
			sb.append(arr[n]).append(' ');
		}
		System.out.print(sb);
	}

}

 

1등 코드

메모리 : 20464 KB

시간 : 248 ms

코드길이 : 3277 B

 

[상위권 코드]

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

class Main {

    public static void main(String[] args) throws Exception {

        int N = read();
        int top = N;
        int[] input = new int[N];

        final int MAX_INDEX = 1_000_000 << 3;
        int pointer = MAX_INDEX;
        char[] buffer = new char[pointer];

        for (int i = 0; i < N; i++) input[i] = read();

        for (int i = N; i-- > 0;) {
            while (top < N && input[top] <= input[i]) top++;
            if (top >= N) {
                buffer[--pointer] = 49;
                buffer[--pointer] = 45;
            } else {
                int num = input[top];
                do {
                    buffer[--pointer] = (char) (num % 10 + 48);
                } while ((num /= 10) > 0);
            }
            buffer[--pointer] = 32;
            input[--top] = input[i];
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(buffer, ++pointer, MAX_INDEX - pointer);
        bw.close();

    }

    static int read() throws Exception {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

[틀렸는데 왜 틀린지 모르겠는 코드]

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();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		Stack<Integer> stack = new Stack<>();
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			stack.push(Integer.parseInt(st.nextToken()));
		}
		Stack<Integer> NGE = new Stack<>();
		NGE.push(-1);
		
		while(stack.size() > 1) {
			int max = stack.pop();
			if(stack.peek() < max) {
				NGE.push(max);
			}
			else {
				if(NGE.peek() > stack.peek())
					NGE.push(NGE.peek());
				else 
					NGE.push(-1);
			}
		}
		
		while(!NGE.isEmpty()) {
			sb.append(NGE.pop()).append(" ");
		}
		System.out.print(sb);
	}

}