[BOJ] 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)을 공백으로 구분해 출력한다.

해결 방법

• 계속 시간 초과가 떠서 Stack을 사용
• 틀렸습니다가 떴을 때 다음 반례가 도움이 되었다
  11
  1 10 999999 7 999998 3 1 4 1000000 3 1000000
• 임시스택을 업데이트를 안 시켜주었기 때문 -> while문 추가해서 pop 해야함
• 접근 방법
  • 입력 값을 배열의 뒷자리부터 채웠다 <- stack을 pop 했을 때 순서대로 출력하기 위함
  • 임시스택과 결과스택 두 개를 만듦
  • for문을 돌린다
  • 임시스택의 값들이 arr[i]보다 작거나 같으면 임시스택을 pop한다
  • if 임시스택이 비어있으면 결과스택에 -1을 넣고 임시스택에 arr[i]를 넣는다
  • else if 임시스택의 peek이 arr[i] 보다 크면 -> 결과스택에 큰 값을 넣고 임시스택에 arr[i]를 넣는다
  • else if arr[i]보다 결과스택의 peek이 더 크면 -> 결과스택에 큰 값을 넣고 임시스택에 arr[i]를 넣는다
  • else arr[i]가 임시스택의 peek과 결과스택의 peek보다 더 크면 -> 결과스택에 -1을 넣고 임시스택에 arr[i]를 넣는다
  • 결과스택을 출력한다.

    public class Week02_17298 {
    public static void main(String[] args) throws IOException {
      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<Integer> stack_tmp = new Stack<>();
      Stack<Integer> stack_res = new Stack<>();
      int[] arr = new int[n];
      // 거꾸로된 입력배열 생성
      for (int i = arr.length - 1; i >= 0; i--) {
          arr[i] = Integer.parseInt(st.nextToken());
      }
      // main logic
      for (int i = 0; i < arr.length; i++) {
          while (!stack_tmp.isEmpty() && stack_tmp.peek() <= arr[i]) {
              stack_tmp.pop();
          }
          if(stack_tmp.isEmpty()) stack_res.push(-1);
          else if (stack_tmp.peek() > arr[i]) stack_res.push(stack_tmp.peek());
          else if (arr[i] < stack_res.peek()) stack_res.push(stack_res.peek());
          else stack_res.push(-1);
          stack_tmp.push(arr[i]);
      }
      // output
      while (!stack_res.isEmpty()) {
          bw.write(stack_res.pop()+" ");
      }
      bw.flush();
      stack_res.clear();
      bw.close();
      br.close();
    }
    }