[BOJ] 백준 14427번 수열과 쿼리 15 (Java)

#14427 수열과 쿼리 15

난이도 : 골드 1

유형 : 세그먼트 트리

14427번: 수열과 쿼리 15

▸ 문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다.

수열의 인덱스는 1부터 시작한다.

▸ 입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리가 주어진다.

▸ 출력

2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

 

문제 풀이  

최소 인덱스 트리로 설계해줘야 한다. 수열을 비교해서 최솟값을 지니는 인덱스를 세그먼트 트리에 넣어주면 된다. 1번 쿼리는 값을 변경하는 쿼리이고, 2번 쿼리는 단순 루트 트리를 불러오는 것이기 때문에 인덱스 트리 생성과 변경 로직만 잘 작성해주면 된다.

 

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

 

예제를 바탕으로 처음 인덱스 트리 초기화하면 다음과 같이 생성된다.

 

최소  인덱스 트리

 

값 변경하기 (1 5 3)

값 변경도 수열을 비교한 다음 그에 해당하는 인덱스를 넣어주면 된다. 예를 들어 5번 노드를 3으로 바꾼다고 하면 다음과 같이 업데이트된다.

 

값 변경하기

 

 

풀이 코드 

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

public class Main {

	static int[] arr, tree;
	static int n;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n+1];
		tree = new int[4*n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr[0] = Integer.MAX_VALUE;
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		init(1, n, 1);
		StringBuilder sb = new StringBuilder();
		int m = Integer.parseInt(br.readLine());
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			
			if(op == 1) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr[a] = b;
				update(1, n, 1, a);
			}else {
				sb.append(tree[1]+"\n");
			}
		}
		
		System.out.println(sb.toString());
		
	}

	
	static int init(int s, int e, int node) {
		if(s == e) return tree[node] = s;
		
		int mid = (s+e)/2;
		int left = init(s, mid, node*2);
		int right =  init(mid+1, e, node*2+1);
		return tree[node] =  getIndex(left,right); 
	}
	
	static int update(int s, int e, int node, int idx) {
		if(s > idx || e < idx ) return tree[node];
		if(s == e)  return tree[node] = idx;
		
		int mid = (s+e)/2;
		int left = update(s, mid, node*2, idx);
		int right =  update(mid+1, e, node*2+1, idx);
		return tree[node] = getIndex(left,right);
	}
	
	static int getIndex(int left, int right) {
		if(arr[left] == arr[right]) return getMin(left, right);
		else if(arr[left] < arr[right]) return left;
		else return right;
	}
	
	static int getMin(int left, int right) {
		if(left < right) {
			return left;
		}else return right;
	}
	
}