백준 17298번 : 오큰수 java

이 문제는 자료구조 중에서 스택을 이용하여 푸는 문제입니다.

이 문제를 풀 때 해당 인덱스의 수보다 오른쪽에 있으면서 해당 수보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾으면 됩니다.

이를 위해서는 입력받은 수들을 먼저 배열에 넣은 후 0번 index부터 차례대로 값을 stack에 넣습니다.

그리고 stack에 새로 들어오는 값이 이전에 있던 값보다 작다면 이전에 있던 값을 pop하지 않고 새로운 값을 add합니다.

만약 새로 들어오는 값이 이전에 있던 값보다 작다면 우리가 찾던 오큰수이므로 answer배열에 그 값을 넣어줍니다.

이 과정을 그림을 통해서 설명드리겠습니다.

예제 1번을 예시로 풀어보겠습니다.

0번 index는 stack에 비교할 값이 없기 때문에 그 값을 바로 stack에 넣어줍니다.

1번 index로 이동하여 stack에 값을 넣으려 하면 원래 있던 값인 3이 5보다 작습니다.

따라서 5는 3의 오큰수 이므로 3을 pop해주고 3이 있던 자리인 answer의 0번 index를 5로 초기화해줍니다.

2번 index로 이동하면 새로 들어오는 값이 2입니다.

Stack에 원래 있던 값은 5이므로 새로 들어오는 값이 원래 있던 스택의 값보다 작습니다.

따라서 5를 pop하지 않고 2를 stack에 add해줍니다.

이제 3번 index가 들어왔습니다.

Stack에 있던 값들을 차례대로 peek해볼 때 2는 7보다 작습니다.

따라서 2의 index가 2이므로 answer의 2번 자리를 7로 바꿔주고 Stack을 pop합니다.

Stack에서 데이터를 한번 pop했으니 다시 남아있는 값과 비교해줍니다.

5보다 새로 들어온 값인 7이 더 크므로  stack을 다시 pop해줍니다.

또한 5의 index인 1번 자리에 7을 넣어줍니다.

그리고 이제 stack이 비었기 때문에 비교할 값이 없으므로 7을 stack에 add해줍니다.

이제 새로 들어오는 수가 없으므로 7의 오큰수를 찾을 수가 없습니다.

따라서 문제의 조건에 따라 stack에 남아있는 자료들의 index에는 -1을 넣어줍니다.

이제 문제에서 원하는 답이 만들어졌습니다.

이 과정을 코드로 보여드리겠습니다.

---

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));
        StringBuffer sb = new StringBuffer();

        int N = Integer.parseInt(br.readLine());
        int[] data = new int[N];

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

        Stack<Integer> s = new Stack<>();

        for(int i = 0; i<N; i++){

            while(!s.isEmpty() && data[s.peek()] < data[i]){
                data[s.pop()] = data[i];
            }

            s.add(i);
        }

        while(!s.isEmpty())
            data[s.pop()] = -1;

        for(int i = 0; i<N; i++)
            sb.append(data[i]).append(" ");

        System.out.println(sb);
    }
}

저는 data 배열이 한번 index가 지나가면 다시 사용하지 않기 때문에 이 배열에 위에서 설명했던 answer의 값을 다시
넣었습니다.