백준 17298번 ) 오큰수 (java)

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

17298번: 오큰수

 

문제

 

풀이

 

Stack을 사용해서 푸는 문제이다.

입력받은 배열에서 순서대로, 스택의 top에 위치하는 수보다 더 작으면 stack에 인덱스를 넣고, 더 큰 경우 해당하는 인덱스의 배열보다 큰 가장 왼쪽의 수이므로 배열에 바로 입력한다.

 

이해하고나면 쉬운데, 스택의 특징을 잘 생각해서 for 문을 두번 돌지 않도록 효율적으로 떠올릴 수 있는지를 생각해내야하는 문제이다.

 

코드

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));
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<Integer>();
        int[] seq = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i< N; i++){
            seq[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++){
            while(!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
                seq[stack.pop()] = seq[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()) {
            seq[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            sb.append(seq[i]).append(' ');
        }

        System.out.println(sb);

    }
}

 

StringBuilder를 사용해 한번에 출력할 수 있도록 하는 연습을 하자!!

sb.append()