백준 17298. 오큰수

문제 : 백준 17298. 오큰수

문제

입력

출력

풀이

아! 한번 풀고도 다시 푸는데 풀이가 생각이 안난다. 나중에 다시 풀어도 풀이 생각이 안날듯
어떻게 접근했어야하는지, 어떤 풀이방식으로 접근했는지 위주로 작성해봐야겠다.

ex) n= 4, A = [3, 5, 2, 7]
Stack = [] # 스택에는 A의 인덱스를 저장합니다.
ans = []

i = 0 부터 i = n 까지 탐색한다.
스택이 비어있지 않고 스택의 top보다 arr[i]가 더 크면 오큰수가 되기 때문에 
top의 오큰수(= arr[i])를 ans에 저장해준다.
ans[stack.pop()] = arr[i]

스택을 pop했기 때문에 다음 스택의 top에 대해서도 같은 작업을 반복한다.

아! 오키
우선 이 문제를 스택으로 접근할 생각부터 해야겠다. 스택으로 접근하고, 그 다음 스택에 먼저 이전 값들을 넣을 수 있는 행위를 해야겠다.
이전 값들을 넣었으면 다음값과 비교를 하면서 다음값도 넣을지 말지를 판단해야겠다.
스택 문제에서는 스택의 top이 조건을 만족하는지 안하는지를 판단하고, 조건이 만족되지 않으면 push하고 만족하면 pop을 해주는 식으로 stack을 비워나가도록 해야겠다. 이상!

풀이 코드 java

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class boj17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                ans[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            ans[stack.pop()] = -1;
        }
/*

        for (int an : ans) {
            System.out.print(an + " ");
        }
*/
        //System.out.println();

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++) {
            bw.write(ans[i] + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}

풀이 코드 python

n = int(input())
arr = list(map(int, input().split()))
ans = [-1 for i in range(n)]

stack = [] # 수열의 인덱스를 저장하는 스택
stack.append(0) # 첫번째 인덱스 추가
for i in range(1, n):
    while stack and arr[stack[-1]] < arr[i]:
        ans[stack.pop()] = arr[i]
    stack.append(i)
#
# while stack:
#     ans[stack.pop()] = -1

for i in ans:
    print(i,end=" ")