[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.