[알고리즘] 17298번

._mung·2024년 2월 17일

Algorithm

목록 보기

20/56

오늘 풀어볼 문제는 백준 17298번 문제 "오큰수" 이다.

이 문제는 골드4 문제이고 스택 문제이다.

문제

크기가 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)을 공백으로 구분해 출력한다.

📌첫 번째 도전📌
문제 자체 정말 단순했다. 그냥 for문 두 개를 만들어서 현재 인덱스 값과 현재 인덱스 기준으로 오른쪽 값들과 값을 계속 비교해 나가면서 정답 배열에 넣어주고 출력하면 끝이라고 생각했다. 하지만.. 이렇게 쉬운 문제가 골드일리가 없었다.
그래서 시간 제한을 찾아보니 1초였다. 저번에 1초인 문제를 풀어보았는데 정말 시간적인 부분을 신경을 써야 한다는 것을 깨달았다. 문제 유형이 스택인 만큼 스택을 최대한 활용해서 문제를 풀어나가야겠다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N]; // 3 5 2 7
        int[] result = new int[N]; // 5 7 7 -1
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

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

        for(int i=0; i<N; i++) {
            System.out.print(result[i]+ " ");
        }
    }
}

첫 번째 풀이는 for문 안에 while문을 넣어 현재 값과 스택에 peek 값을 비교해 나가면서 result에 저장하는 방식을 택했다.
방향을 맞았지만 시간 초과로 실패했다.
아마 시간을 더 줄이는 방법은 출력 방식을 바꾸는 방법 밖에 떠오르지 않았다.

📌두 번째 도전📌

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N]; // 3 5 2 7
        int[] result = new int[N]; // 5 7 7 -1
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

        while(!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i=0; i<N; i++) {
            bw.write(result[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}