Post

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

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

문제 링크


1. 아이디어

stk가 비었거나 마지막 원소가 arr[i]보다 작으면 arr[i]를 stk에 붙이고 $i$를 하나 올리며, 아니면 마지막 원소를 지운다. 이렇게 쌓이는 stk는 아래에서 위로 갈수록 값이 커지는 단조 스택이고, 이 규칙을 그대로 시뮬레이션하면 된다. 다만 지우는 단계에서는 $i$가 늘지 않아 반복 횟수가 arr의 길이를 넘을 수 있다. 그래도 arr의 원소는 stk에 한 번만 붙고 지울 수 있는 것은 붙은 원소뿐이므로, arr의 길이를 $N$이라 하면 반복은 많아야 $2N$번이라 길이가 10만이어도 충분하다.


2. 코드

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

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--;
            }
        }

        return Arrays.copyOf(stk, idx);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
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

This post is licensed under CC BY 4.0 by the author.