[백준 - 17298번] 오큰수 -Java //Wello Horld//

이번엔는 BOJ의 17298번 오큰수를 풀어보도록 하자

일단 크기가 N인 수열 A 를 입력으로 받고 각 원소 Ai 에 대해서 오른쪽에 있으면서 해당 원소보다 큰 가장 왼쪽에 있는 수를 출력하는 문제이다. 문제자체는 간단한데, 시간제한은 1초로 짧고, 입력으로 주어지는 수열A의 크기가 1,000,000(백만) 으로 꽤나 크다는 것을 알 수 있다. 즉, 그냥 루프로 돌려버리면 안된다는 것이다.

일단, 개삽질했다... 머리가 나빠서 그런지 될 것 같은데 계속 안되서 컴퓨터 부실뻔하다가 다시 처음부터 마음을 가다듬고 만들었다.

일단, 입력값을 받는 루프안에 모든 것을 해결하려고 했다. 그래서, LIFO 방식인 Stack을 이용해서 이전 값들을 비교하는 방식을 선택했다. 먼저, Int배열인 ans배열을 만들어 주었다. 그리고 InputA라는 클래스를 만들어 주어서, 입력받은 값의 위치와 원소값을 집어넣어서, ans에 들어갈 값들을 변형 시켜주는 방식으로 해결책을 찾았다. 시간은 오지게 걸렸지만, 맞았으니.... 좀더 효율적으로 계산할 수 있는 방식을 생각해 봐야겠다.

성공한코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<InputA> stack = new Stack<InputA>();
        int[] ans = new int[N];
        Arrays.fill(ans, -1);
        for (int i = 0; i < N; i++) {
            int element = Integer.parseInt(st.nextToken());
            if(!stack.isEmpty()) {
                InputA compVal = stack.peek();
                if(compVal.element < element) {
                    while(!stack.isEmpty()) {
                        compVal = stack.pop();
                        if(compVal.element < element){
                            ans[compVal.position] = element;
                        } else {
                            stack.add(compVal);
                            break;
                        }
                    }
                    stack.add(new InputA(element, i));
                } else {
                    stack.add(new InputA(element, i));
                }
            } else {
                stack.add(new InputA(element, i));
            }
        }
        bw.write(Arrays.toString(ans).replaceAll("\\[|\\]|,|", "") + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}
class InputA{
    int element, position;
    public InputA(int element, int position){
        this.element = element;
        this.position = position;
    }
}

 

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