Stack을 이용한 오큰수 구현

💡 Stack을 이용한 오큰수 구현

for문으로 오큰수를 찾으면 시간복잡도가 높아 제한시간을 초과할 우려가 있으므로,

스택을 이용하여 오큰수를 구현한다.

 

입출력 예시

입력

int N = 수열의 크기

int[] M = 수열'

 

출력

5 7 7 -1

 

풀이

스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.

오큰수를 구한 후, 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다.

 

풀이 순서

• 스택에 채워져 있거나 A[index] > A[top]인 경우 pop한 인덱스를 이용해 정답 수열에 오큰수 저장.
  (pop은 조건을 만족하는 동안 계속 반복)
• 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어간다.
• 위의 과정을 수열의 길이만큼 반복하고 현재 스택에 남아있는 인덱스에 -1을 저장한다.

    public int O(int a, int[] b, String[] c) {
        // 수열 배열 생성
        int[] A = new int[a];
        // 정답 배열 생성
        int[] B = new int[a];

        for (int i = 0; i < a; i++) {
            A[i] = Integer.parseInt(c[i]);
        }

        // 스택의 최초값을 0 으로 초기화
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 0; i < a; i++) {
            // 스택이 비어있지 않고 현재 수열이 스택의 top이 가리키는 수열보다 클 경우
            while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
                // 정답 배열에 오큰수를 현재 수열로 저장
                B[stack.pop()] = A[i];
            }
            // 신규 데이터 push
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            // 반복문을 다 돌았는데 스택이 비어 있지 않다면 빌때까지
            // 스택에 쌓인 인덱스에 -1을 넣는다
            B[stack.pop()] = -1;
        }

        int temp = 0;
        for (int i = 0; i < a; i++) {
            temp = B[i];
            System.out.println(temp + " ");
        }

        return temp;
    }