[P&B] #5 Programmers

프로그래머스 Lv.2 스택, 우선순위큐

 

뒤에 있는 큰 수 찾기

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

나의 문제 풀이 코드 (82.6/100_시간초과)

public static int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            if (i == numbers.length-1){
                answer[i] = -1;
                break;
            }
            for (int j = i+1; j < numbers.length; j++) {
                if (numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
                else if (numbers[i] > numbers[j])
                    answer[i] = -1;
            }
        }
        return answer;
    }

 

답안 참고 후 수정한 코드

import java.util.*;

class Solution {
    public static int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> s = new Stack<>();

        for(int i=numbers.length-1; i>=0; i--){
            while(!s.isEmpty()){
                if(s.peek() > numbers[i]){
                    answer[i] = s.peek();
                    break;
                }else{
                    s.pop();
                }
            }
            if(s.isEmpty()){
                answer[i] = -1;
            }
            s.push(numbers[i]);
        }
        return answer;
    }
}

 

문제 풀이 코멘트

스택이나 우선순위큐를 사용하여 풀어야함을 알고있음에도 불구하고 도저히 알고리즘들을 적용한 구현 방식이 생각나지 않아 결국 이중포문을 사용하여 풀게되었다. 아니나 다를까 제한 사항에서 배열의 최대 길이가 1,000,000이라서 O(n^2) 로직으로는 시간 초과가 발생했다. 결국 20~23번은 시간초과로 통과하지 못했고 아직은 우선순위 큐 보단 스택이 이해하기 더 편해서 스택으로 구현된 답안 코드를 보았다. 스택으로 푼 문제들 중에 스택 자체를 numbers 배열의 인덱스로 하여 푼 코드들이 다수 보였는데 그렇게 되면 개인적으로 두번 꼬아서 생각을 해야하는 것처럼 느껴졌다. 그래서 스택을 배열의 값으로 하여 구현한 코드로 이해했다. 위 코드에서는 스택이 비어있지 않은 경우, 스택을 peek으로 확인하여 그 값이 배열값 보다 크다면 answer에 담아주고 배열값 보다 작다면 pop을 하며 다음 원소를 검사한다 만약 스택에 아무것도 없다면 answer 배열엔 -1을 넣고 스택에 numbers 배열값을 push한다. 왜 생각이 안나지.. 나중에 다시 풀어봐야겠다.