2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
탑 A의 왼쪽에 있는 탑들 중에서 탑 A보다 더 큰 높이의 탑들 중 가장 오른쪽의 탑의 위치를 구하는 문제입니다.
배열크기를 너무 높게잡으면 메모리초과까지 나올 수 있어서 초기에 배열크기를 잘 잡아야합니다.
N이 500000까지 들어오기때문에 N^2으로는 무조건 시간초과뜹니다
먼저 입력으로 주어지는 탑의 높이를 list에 저장하였고, 1번부터 N번까지 순회를 합니다.
스택에는 인덱스를 유지합니다.
i번 위치에서 스택이 비어있지 않고, list[top]이 list[i]보다 작을동안 pop을 해줍니다.
그 후에 스택이 비어있으면 0, 아니면 스택의 top을 출력하시면 됩니다.
|
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
|
package BOJ.data_structure;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Boj2493 {
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[];
static int N;
static void func() {
for (int i = 0; i < N; i++) {
while (!s.isEmpty() && list[s.peek()] < list[i])
s.pop();
if (s.isEmpty()) {
s.push(i);
sb.append("0 ");
} else {
sb.append(s.peek() + 1 + " ");
s.push(i);
}
}
System.out.println(sb.toString());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = 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();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 1918 후위 표기식 (0) | 2021.02.05 |
|---|---|
| boj 1935 후위 표기식2 (0) | 2021.02.05 |
| boj 6416 트리인가? (0) | 2021.02.04 |
| boj 3190 뱀 (0) | 2021.02.02 |
| boj 2346 풍선 터뜨리기 (0) | 2021.02.02 |