99클럽 코테 스터디 1일차 TIL / [프로그래머스] 뒤에 있는 큰 수 찾기

오늘의 학습 키워드

---

Stack

문제

---

• 플랫폼: 프로그래머스
• 문제명: 뒤에 있는 큰 수 찾기
• 난이도: Lv2

풀이

---

import java.util.*;

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

접근

• 제한사항에서 numbers 배열의 길이가 최대 1,000,000 까지 가질 수 있었기에, 최대 O(log(n))의 시간 복잡도의 풀이를 작성하는 것을 목표로 했습니다.
• 문제는 앞에서부터 순회하면서 가장 가까운 큰 수를 찾아야 하는 문제로, Stack에 하나씩 넣어가며 Stack에 들어있는 값보다 큰 수가 들어오면 더 큰 수가 있기 전까지 pop하는 형태로 구현했습니다.
• 순회가 종료된 후 스택에 남아있는 원소들은 자신의 뒤에 더 큰 수가 존재하지 않는 것이므로, -1로 채워줬습니다.

소요 시간

10분

회고

---

시간 복잡도 최적화 상황에서 순회 혹은 그 뒤의 원소를 비교하는 특징이 있다면, 스택을 고려해 볼 것!