ALGORITHM/BOJ
[백준] 5676 음주 코딩
0298
2021. 2. 7. 16:55
5676번: 음주 코딩
각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.
www.acmicpc.net
2021-02-07
|
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, K, arr[], tree[];
public static int init(int node, int start, int end) {
// leaf node
if(start == end) return tree[node] = arr[start];
int mid = (start + end) / 2;
return tree[node] = init(node*2, start, mid) * init(node*2+1, mid+1, end);
}
public static void update(int node, int start, int end, int idx, int change) {
// idx out of range
if(start > idx || end < idx) return;
// leaf node
if(start == end) {
tree[node] = change;
return;
}
// not leaf node
if(start != end) {
int mid = (start + end) / 2;
update(node*2, start, mid, idx, change);
update(node*2+1, mid+1, end, idx, change);
tree[node] = tree[2*node] * tree[2*node+1];
}
}
public static long multiple(int node, int start, int end, int left, int right) {
// 1) left, right가 start, end 범위를 완전히 벗어났을 때
if(left > end || right < start) return 1;
// 2) left, right가 start, end를 완전히 포함하는 경우
if(left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
return multiple(node*2, start, mid, left, right) *
multiple(node*2+1,mid+1, end, left, right);
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String temp;
while((temp = bf.readLine()) != null) {
StringTokenizer st = new StringTokenizer(temp);
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N+1];
tree = new int[N*4];
st = new StringTokenizer(bf.readLine());
// 루트 노드는 1부터 시작한다.
for(int i = 1; i <= N; i++) {
int x = Integer.parseInt(st.nextToken());
if(x > 0) arr[i] = 1;
else if(x < 0) arr[i] = -1;
else arr[i] = 0;
}
// init
init(1, 1, N);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < K; i++) {
st = new StringTokenizer(bf.readLine());
String order = st.nextToken();
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(order.equals("C")) { // change arr[a] <- b
if(b > 0) b = 1;
else if(b < 0) b = -1;
update(1, 1, N, a, b);
} else { // delete
long answer = multiple(1, 1, N, a, b);
if(answer > 0) sb.append("+");
else if(answer < 0) sb.append("-");
else sb.append("0");
}
}
System.out.println(sb.toString());
}
}
}
|
cs |
#문제풀이
세그먼트 트리 문제이다. 일종의 구간 곱 구하기 인데, 입력값에서 받은 값 그대로 사용하면 스택오버플로우가 생긴다.
그래서 각 값을 양수/음수/0으로 나누어서 아래와 같이 입력 값을 받고, update 할 때도 양수/음수/0으로 나누어서 그 값으로 값을 변경해야한다.
양수 -> 1
음수 -> -1
0 -> 0