[BOJ] 백준 5676번 음주 코딩 (Java)

#5676 음주 코딩

난이도 : 골드 1

유형 : 세그먼트 트리

5676번: 음주 코딩

▸ 문제

오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다.

상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다.

먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다.

• 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다.
• 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다.

곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다. 상근이는 갑자기 대회가 걱정되기 시작했다. 또, 상근이는 발머의 피크 이론을 증명하고 싶지 않다.

다행히 선영이는 상근이에게 노트북 사용을 허락했다. 상근이는 자신의 수학 실력보다 코딩 실력을 더 믿는다.

상근이를 돕는 프로그램을 작성하시오.

▸ 입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 수열의 크기 N과 게임의 라운드 수 K가 주어진다. (1 ≤ N, K ≤ 105)

둘째 줄에는 총 N개의 숫자 Xi가 주어진다. (-100 ≤ Xi ≤ 100)

다음 K개 줄에는 선영이가 내린 명령이 주어진다. 명령은 C 또는 P로 시작한다.

C로 시작하는 명령은 변경 명령이고, 그 다음에 i와 V가 주어진다. Xi를 V로 변경하는 명령이다. (1 ≤ i ≤ N, -100 ≤ V ≤ 100)

P로 시작하는 명령은 곱셈 명령이고, 그 다음에 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

각 테스트 케이스에 곱셈 명령은 항상 한 번 이상있다.

▸ 출력

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

 

문제 풀이  

세그먼트 트리 기본 유형이다. 다만 곱 세그먼트 트리이기 때문에 오버플로에 조심해야 한다. 어차피 부호를 나타내는 문제이므로 양수이면 1, 0이면 0, 음수이면 -1로 축소하여 계산할 수 있다.

 

세그먼트 트리에 대한 자세한 설명은 여기를 참고해주세요

 

첫 번째 예제로 곱 세그먼트 트리를 만들면 다음과 같이 생성된다.

곱 세그먼트 트리

 

 

그리고 입력의 끝이 주어져있지 않기 때문에 그냥 try-with-resources문을 사용해서 에러가 발생하면 finally에서 출력해주면 된다.

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
	while((line = br.readLine()) != null) {
		st = new StringTokenizer(line);
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
        // ...
	}
} catch(Exception e) {
//	e.printStackTrace();
} finally {
	System.out.println(sb.toString());
}

 

 

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int[] arr, tree;
	public static void main(String[] args){
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		String line;
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
			while((line = br.readLine()) != null) {
				st = new StringTokenizer(line);
				
				int n = Integer.parseInt(st.nextToken());
				int k = Integer.parseInt(st.nextToken());
				
				arr = new int[n];
				tree = new int[n*4];
				st = new StringTokenizer(br.readLine());
				for(int i=0; i<n; i++) {
					int num = Integer.parseInt(st.nextToken());
					setStatus(i, num);
				}
			
				init(0, n-1, 1);
				for(int i=0; i<k; i++) {
					st = new StringTokenizer(br.readLine());
					String op = st.nextToken();
					int a = Integer.parseInt(st.nextToken())-1;
					int b = Integer.parseInt(st.nextToken());
					if(op.equals("C")) {
						setStatus(a, b);
						update(0, n-1, 1, a);
					}else {
						int c = query(0, n-1, 1, a, b-1);
						if(c < 0) {
							sb.append("-");
						}else if (c > 0) {
							sb.append("+");
						}else {
							sb.append("0");
						}
					}
				}
				sb.append("\n");
			}
		}catch(Exception e) {
//			e.printStackTrace();
		} finally {
			System.out.println(sb.toString());
		}
	}
		
	static void setStatus(int idx, int num) {
		if(num < 0 ) {
			arr[idx] = -1;
		} else if (num > 0) {
			arr[idx] = 1;
		}else {
			arr[idx] = 0;
		}
	}
	
	static int init(int s, int e, int node) {
		if(s == e) return tree[node] = arr[s];
		int mid = (s+e)/2;
		return tree[node] = init(s, mid, node*2)* init(mid+1, e, node*2+1); 
	}
	
	static int update(int s, int e, int node, int idx) {
		if(idx < s || e < idx) return tree[node];
		if(s==e) return tree[node] = arr[idx];
		
		int mid = (s+e)/2;
		return tree[node] = update(s, mid, node*2, idx)* update(mid+1, e, node*2+1, idx);
	}
	
	static int query(int s, int e, int node, int l, int r) {
		if( r < s || e < l) return 1; 
		if(l <= s && e <= r) {
			return tree[node];
		}
		
		int mid = (s+e)/2;
		return query(s, mid, node*2, l, r)*query(mid+1, e, node*2+1, l, r);
	}
}