개발/문제해결

[백준] 5676번 : 음주 코딩

hyosupsong 2021. 2. 5. 22:33

문제

www.acmicpc.net/problem/5676

 

5676번: 음주 코딩

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

www.acmicpc.net

문제해결방법

이 문제는 세그먼트 트리로 구간의 곱을 구해놓고 값을 변경시켜주면서 풀었다.

코드

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
package baekjoon;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main5676_음주코딩 {
    public static int[] XI, segmentTree;
 
    public static int getNumberSign(int number) {
        if(number>0) return 1;
        else if(number<0) return -1;
        else return 0;
    }
 
    public static void makeTree(int index, int s, int e) {
        if(s==e) {
            segmentTree[index] = XI[s];
            return; 
        }
        int mid = (s+e)>>1;
        makeTree(index*2, s, mid);
        makeTree(index*2+1, mid+1, e);
        segmentTree[index] = segmentTree[index*2]*segmentTree[index*2+1];
    }
    
    public static int query(int index, int s, int e, int si, int ei) {
        if(si>e || ei<s) return 1;
        if(si<=s && e<=ei) return segmentTree[index];
        
        int mid = (s+e)>>1;
        return query(index*2, s, mid, si, ei) * query(index*2+1, mid+1, e, si, ei);
    }
    
    public static void update(int index, int s, int e, int ui, int diff) {
        if(ui>e || ui<s) return;
        if(s==e) {
            segmentTree[index]=diff;
            return;
        }
        int mid = (s+e)>>1;
        update(index*2, s, mid, ui, diff);
        update(index*2+1, mid+1, e, ui, diff);
        segmentTree[index] = segmentTree[index*2] * segmentTree[index*2+1];
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String start;
        while((start = br.readLine())!=null) {
            StringTokenizer st = new StringTokenizer(start);
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            XI = new int[N+1];
            segmentTree = new int[4*N];
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<=N; i++) XI[i] = getNumberSign(Integer.parseInt(st.nextToken()));
            makeTree(1, 1, N);
            for(int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
                char op = st.nextToken().charAt(0);
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                switch(op) {
                case 'P':
                    int result = query(1, 1, N, a, b);
                    if(result>0) bw.write('+');
                    else if(result<0) bw.write('-');
                    else bw.write('0');
                    break;
                case 'C':
                    b = getNumberSign(b);
                    XI[a] = b;
                    update(1, 1, N, a, b);
                    break;
                }
            }
            bw.write('\n');
        }
        bw.flush();
        bw.close();
        br.close();
    }
}
cs

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.