[17298] 오큰수

✔ 오큰수 

[백준 17298]

문제 분석하기

N의 최대 크기가 1000000이므로 반복문으로 오큰수를 찾으면 제한시간이 초과되므로 스택을 사용해 문제에 접근

손으로 풀어보기

1. 스택이 채워져 있고 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장
2. 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감
3. 수열 길이만큼 반복한 다음 현재 스택에 남아 있는 인덱스에 -1을 저장

• 예) [3, 5, 2, 7]

스택
0	1 (push) 0 (pop → 5)	2 (push) 1	3 (push) 2 (pop → 7) 1 (pop → 7)	3 (pop → -1)

0	1	2	3
5	7	7	-1

슈도코드 작성하기

N(수열 개수) A[](수열 배열) ans[](정답 배열)
수열 배열 채우기
최초 스택 초기화하기
for(N만큼 반복) {
    while(스택이 비어 있지 않고, 현재 수열 값이 top에 해당하는 수열보다 클 때까지) {
        pop()
        정답 배열에 오큰수를 현재 수열로 저장하기
    }
    현재 수열을 스택에 push
}
while(스택이 빌 때까지) {
    스택에 있는 인덱스의 정답 배열에 -1 저장하기
}
정답 배열 출력하기

코드 구현하기

/**
 * 17298) 오큰수
 */
public class D012_17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(수열 개수)
        int N = Integer.parseInt(br.readLine());
        // A[](수열 배열)
        int[] A = new int[N];
        // ans[](정답 배열)
        int[] ans = new int[N];
        // 수열 배열 채우기
        String[] str = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(str[i]);
        }
        // 최초 스택 초기화하기
        Stack<Integer> myStack = new Stack<>();
        myStack.push(0);
        for (int i = 1; i < N; i++) {
            // 스택이 비어 있지 않고, 현재 수열 값이 top에 해당하는 수열보다 클 때까지
            while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
                // 정답 배열에 오큰수를 현재 수열로 저장하기
                ans[myStack.pop()] = A[i];
            }
            // 현재 수열을 스택에 push (다음 인덱스의 오큰수 구하기)
            myStack.push(i);
        }
        // 스택이 빌 때까지
        while (!myStack.isEmpty()) {
            // 오큰수가 없어 스택에 남아 있는 인덱스의 정답 배열에 -1 저장하기
            ans[myStack.pop()] = -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();
    }
}