[백준] 17298 오큰수

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

17298번: 오큰수

2022-07-25

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        int N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(bf.readLine());
 
        int[] arr = new int[N];
        // 1) 수열 입력 받기
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
 
        Stack<Integer> s = new Stack<>();
        // 2) stack, 0번째 index push;
        s.push(0);
        int[] answer = new int[N];
 
        for(int i = 1; i < N; i++) {
            if(s.isEmpty()) s.push(i);
 
            // 3) stack이 비어있지 않고, 현재 stack의 top에 있는 index의 값과 현재 index와 비교
            while(!s.isEmpty() && arr[s.peek()] < arr[i]) {
                answer[s.pop()] = arr[i];
            }
            s.push(i);
        }
 
        // 4) 끝까지 다 체크 했는데 아직 stack에 index가 남아있는 경우
        while(!s.isEmpty()) {
            answer[s.pop()] = -1;
        }
 
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < answer.length; i++) sb.append(answer[i]).append(" ");
 
        System.out.println(sb.toString());
    }
}

#문제풀이

 

시간초과와 틀렸습니다를 반복하고 결국 블로그를 찾아봤다. 알고 나니 왜 value가 아닌 index를 사용할 생각을 못했지라는 생각이 들었다. 

 

이 문제는 stack에 index값을 넣어서 풀 수 있는 문제이다. 

처음 입력 받은 arr와 index 값을 넣을 stack, 그리고 answer 3개를 세트로 생각하고 푼다.

 

1) 수열 입력 받기

2) stack에 0번째 index push 하기 

 

 

 

3) for문을 1부터 n-1까지 돌면서 오큰수를 찾는다.

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

 

 

 

3-1) 위 초기 세팅 기준으로 현재 stack.peek은 index 0이고, for문의 Index값은 1이다.

 

그러면 arr[0] 즉, 3과 arr[1] 즉 5 를 비교할 수 있다. arr[s.peek()] < arr[i] 이므로, arr[0]의 오큰수는 arr[1]이 맞다.

오큰수를 찾았기 때문에 stack에서 pop을 하고, 해당 index값에 오큰수를 부여할 수 있다. 그리고 stack에 남아있는 값이 없어서 while문을 빠져나가게 된다.

 

그리고 다음 index값을 stack에 넣어주었다.

 

 

 

 

 

3-2) 현재 기준으로 stack.peek()은 index 1이고, for문의 index 값은 2 이다.

arr[1]과 arr[2]를 비교하게 되는데 arr[1]은 5이고, arr[2]는 2로 arr[1]이 더 크기 때문에 arr[2]는 arr[1]의 오큰수가 아니다. 

 

 

 

 

 

 

3-3) 현재 기준으로 stack.peek()은 index 2이고, for문의 기준 index값은 3이다. 

arr[2]와 arr[3]을 비교하게 되는데 arr[2]는 2이고 arr[3]은 7이므로 arr[2]의 오큰수는 7이 되고 2는 stack에서 pop된다.

아까 코드를 다시 보면 while문 이므로, 그 다음에 있던 index값 1을 찾을 수 있다. 따라서 arr[1]은 5이고 arr[3]은 7이므로 arr[1]의 오큰수는 7이 되고 stack에서 pop된다.

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

 

 

 

 

3-4) stack에 마지막 index 3이 push가 되었지만, 마지막 index값이라 for문에서 빠져나오게 된다.

 

 

4) for문을 빠져나왔지만 아직 stack에 값이 있으므로, 해당 stack에 있는 모든 값들을 오큰수가 없다고 판단하여 해당 index에 -1로 처리를 해주어야 한다.

while(!s.isEmpty()) {
      answer[s.pop()] = -1;
}