[프로그래머스] 배열 만들기 4

코드 힌트

1. Stack 사용하기: 문제를 해결할 때 스택(Stack) 자료구조를 사용하면 더 간단하게 구현할 수 있습니다. 스택은 LIFO(Last In First Out) 구조로, 마지막에 추가된 원소가 가장 먼저 꺼내집니다.
2. 문제 조건 잘 이해하기: stk에 원소가 있는데 stk의 마지막 원소가 arr[i]보다 크거나 같으면 stk의 마지막 원소를 stk에서 제거합니다. 라는 조건이 있습니다. 해당 조건을 만족한다면 i++를 하라는 조건이 없습니다.
   즉 계속해서 해당 arr[i]에 대해 조건이 맞다면 반복하라는 의미입니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        // 결과를 저장할 Stack 생성
        Stack<Integer> stack = new Stack<>();
        
        // 배열의 각 요소를 순회
        for (int i = 0; i < arr.length; i++) {
            
            // 현재 스택의 최상단 원소가 배열의 현재 원소보다 크거나 같으면 스택에서 제거
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            
            // 스택이 비어있으면 현재 원소를 스택에 추가
            if (stack.isEmpty()) {
                stack.push(arr[i]);
                continue;
            }
            // 현재 원소가 스택의 최상단 원소보다 클 경우 스택에 추가
            else if (stack.peek() < arr[i]) {
                stack.push(arr[i]);
            }
        }
        
        // 결과 배열을 스택의 크기로 초기화
        int[] result = new int[stack.size()];
        
        // 스택에서 원소를 꺼내어 결과 배열에 저장 (스택은 LIFO 구조이므로 역순으로 저장됨)
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = stack.pop();
        }
        
        return result;
    }
}