[java] 문제 012 (백준 17298)

문제

오큰수

 

교재 풀이

import java.util.*;
import java.io.*;
public class P17298_오큰수 {
  public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    int[]A = new int[n];    // 수열 배열 생성
    int[]ans = new int[n]; // 정답 배열 생성
    String[] str = bf.readLine().split(" ");
    for (int i = 0; i < n; i++) {
        A[i] = Integer.parseInt(str[i]);
    }
    Stack<Integer> myStack = new Stack<>();
    myStack.push(0); // 처음에는 항상 스택이 비어있으므로 최초 값을 push하여 초기화
    for (int i = 1; i < n; i++) {
        //스택 비어있지 않고 현재 수열이 스택 TOP인덱스 가르키는 수열보다 크면
        while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {  
            ans[myStack.pop()] = A[i];  //정답 배열에 오큰수를 현재 수열로 저장하기
        }
        myStack.push(i); //신규데이터 push  
    }
    while (!myStack.empty()) {
        // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때 까지
        ans[myStack.pop()] = -1;
        // stack에 쌓인 index에 -1을 넣고
    }
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    for (int i = 0; i < n; i++) {
        bw.write(ans[i] + " ");
        // 출력한다
    }
    bw.write("\n");
    bw.flush();
  }
}

 

설명

• 24.6.4 1차 시도 실패 
  • 스택에 배열의 인덱스를 넣을 생각을 못했네 
  • 그렇지. 어떤 값의 오큰수는 그냥 순서대로 탐색하다가 제일 큰 수가 나온다? 그게 오큰수 아니야.
  • 물론 배열로 하려면 시간 초과라 안 되지만, 스택에 순서대로 수열 배열의 인덱스를 넣으면서 => 조건문으로 계속 a[stack.peek()]과 a[i]를 비교해서, a[stack.peek()] < a[i]일 때가 stack.pop()한 인덱스의 수열의 오큰수 아닌가

교재 보면 다 이해됨 

 

내 풀이

여기에 입력하기