(알고리즘) 백준 17298 java 자바

문제

백준 17298 오큰수 : https://www.acmicpc.net/problem/17298

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

예제입력 1

4
3 5 2 7

예제출력 1

5 7 7 -1

예제입력 2

4
9 5 4 8

예제출력 2

-1 8 8 -1

풀이

해당 문제는 stack을 활용하면 된다
먼저 0번째 부터 stack에 넣어준다 이때 stack의 top보다 작으면 계속 stack에 넣어주고 만일 stack의 top보다 작다면 해당 수의 인댁스의 값에 해당하는 결과 배열에 지금의 값을 바꿔주고 pop을 한다.
이렇게 되면 내 이후 가장 먼저 만나는 나보다 큰 값으로 현재 내 위치의 결과 값이 저장되게 된다.

코드

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

public class Boj17298
{
    static class Info {//수와 인덱스를 저장할 클래스
        int num;
        int idnex;
        public Info(int a,int b){
            num=b;
            idnex=a;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bf.readLine());
        int nums[]=new int[n];
        int ans[]=new int[n];

        StringTokenizer st=new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            nums[i]=Integer.parseInt(st.nextToken());
        }
        Stack<Info> stack=new Stack<Info>();
        stack.push(new Info(0,nums[0]));//0번째를 넣어준다
        for(int i=1;i<n;i++){
            while(!stack.isEmpty()&&stack.peek().num<nums[i]){//스택이 비지 않았고 스택의 top보다 지금의 값이 크면
                ans[stack.peek().idnex]=nums[i];//해당 탑에 해당하는 인덱스의 결과 값을 지금의 값으로
                stack.pop();
            }
            stack.push(new Info(i,nums[i]));//과정이 끝나면 해당 수를 스택에 넣는다
        }
        StringBuilder sb=new StringBuilder();//출력시간 단축을 위해 스트링 빌더 사용
        for(int i=0;i<n;i++){
            if(ans[i]!=0)
                sb.append(ans[i]).append(" ");//값이 있으면 값을 출력
            else
                sb.append("-1 ");//아니면 -1
        }
        System.out.println(sb);
    }
}

후기

해당 문제는 시간초과로 인해 한번 틀렸었다... 문제는 알고보니 출력이 많아서였다. 출력을 StringBuilder로 한번에 만들어서 출력하니 해결...
앞으로 StringBuilder를 활용한 출력에 익숙해져야겠다.
java 입출력이 점점 발전하고 익숙해지고 있다.
와타시 화이팅!