17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
스택으로 구현할 수 있고, 시간초과에 주위해야하는 문제입니다.
자바에서는 출력만으로도 시간초과가 나올 수 있기때문에 반복적인 System.out.println 보다는
StringBuffer, StringBuilder, BufferedWriter 중에서 사용해야합니다.
우선 오큰수는 자신의 오른쪽에 있는 숫자들 중에서 자신보다 큰 수 중에 가장 왼쪽에 있는 수를 말합니다.
저는 이 문제를 해결하기 위해 수열의 역순으로 탐색을 하였습니다.
list[i]를 스택에 넣기 전에 자신보다 작은 값들을 전부 pop해준 후에 남아있는 스택의 top에 있는 값이 오큰수 입니다.
먼저 스택이 비어있다면 자신이 가장 큰 수이므로 -1입니다.
비어있지 않다면 스택의 top이 오큰수입니다.
이 값들을 StringBuffer에 다 append를 해준 후에 마지막에 sb.toString()을 출력해주시면 되겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Stack<Integer> s = new Stack<>();
static int list[], ans[];
static int N;
static void print() {
for (int i = 0; i < N; i++) {
sb.append(ans[i] + " ");
}
System.out.println(sb.toString() + "\n");
}
static void func() {
for (int i = N - 1; i >= 0; i--) {
while (!s.isEmpty() && s.peek() <= list[i])
s.pop();
if (s.isEmpty())
ans[i] = -1;
else
ans[i] = s.peek();
s.add(list[i]);
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N];
ans = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
input();
func();
print();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 6198 옥상 정원 꾸미기 (0) | 2021.01.26 |
|---|---|
| boj 1874 수택 수열 (0) | 2021.01.25 |
| boj 4358 생태학 (0) | 2021.01.25 |
| boj 5639 이진 검색 트리 (0) | 2021.01.24 |
| boj 1991 트리 순회 (0) | 2021.01.22 |
