[Programmers] #181918 - 배열 만들기 4 [Java][C++][Python]

문제 링크

---

1. 아이디어

arr을 순회하면서 stk을 채우는 과정 자체가 이미 답을 만드는 알고리즘이다. 원소를 하나씩 보되, stk이 비어 있거나 arr[i]가 stk의 마지막 원소보다 크면 그대로 stk에 추가하고 다음 원소로 넘어간다. 반대로 arr[i]가 마지막 원소보다 작거나 같으면 인덱스는 그대로 둔 채 stk의 마지막 원소만 제거하고, 같은 arr[i]를 새로운 마지막 원소와 다시 비교한다. 이 규칙을 지키면 stk에는 항상 오름차순으로 증가하는 값만 남는데, 순증가를 깨뜨릴 만한 원소가 들어오면 그 직전 원소를 먼저 밀어내기 때문이다. 원소 하나는 stk에 최대 한 번 들어가고 최대 한 번 나가므로, 전체 순회는 $O(N)$에 끝난다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = arr의 길이)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int[] solution(int[] arr) {
        int[] stk = new int[arr.length];
        int i = 0;
        int idx = 0;

        while (i < arr.length) {
            if (idx == 0 || stk[idx - 1] < arr[i]) {
                stk[idx++] = arr[i++];
            } else {
                idx--;
            }
        }

        int[] ans = new int[idx];
        System.arraycopy(stk, 0, ans, 0, idx);
        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr) {
    vector<int> stk;
    int i = 0;

    while (i < arr.size()) {
        if (stk.empty() || stk.back() < arr[i]) {
            stk.push_back(arr[i++]);
        } else {
            stk.pop_back();
        }
    }

    return stk;
}

def solution(arr):
    stk = []
    i = 0

    while i < len(arr):
        if not stk or stk[-1] < arr[i]:
            stk.append(arr[i])
            i += 1
        else:
            stk.pop()

    return stk

---