[Programmers] 뒤에 있는 큰 수 찾기 / ❌

프로그래머스

 

1. 제출 코드 (30분 44초 / Stack)

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        Arrays.fill(answer, -1);
        
        for(int i = 0; i < numbers.length; i++) {
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        
        return answer;
    }
}

 

2. 구현 로직

1. 정답 배열에 초기 값을 -1로 셋팅
2. 스택의 가장 위에 있는 인덱스의 number가 현재 인덱스의 number보다 작을 때까지 반복
   1. 스택의 가장 위에 있는 인덱스의 정답 배열을 현재 인덱스의 number로 업데이트
3. 스택에 아직 찾지 못한 수의 인덱스 추가

3. 풀이 회고

• numbers의 배열 크기가 1,000,000 인 것을 보고 시간복잡도가 O(n)을 만족해야 될 거같다고 생각했다.
• 특정한 알고리즘을 적용해야 문제를 풀 수 있을 거 같아서 계속해서 생각해봤는데 도저히 풀 수 없을 것 같았다.
• 다른 사람들의 풀이에서 사용한 자료구조를 참고해서 로직을 구현했다.