BOJ_23829_인문예술탐사주간 (Java)

[Gold IV] 인문예술탐사주간 - 23829

문제 링크

성능 요약

메모리: 45380 KB, 시간: 684 ms

분류

이분 탐색, 누적 합

제출 일자

2024년 12월 31일 14:48:28

문제 설명

태영이는 SASA의 축제라고 불리는 “인문예술탐사주간”을 보내게 되었다. “인문예술탐사주간”을 맞이하여 세종호수공원에 가게 된 태영이는 아름다운 경치에 놀라움을 금치 못했다.

세종호수공원은 일직선으로 뻗어있는 모습이다. 이 공원에는 나무가 총 $N$ 그루 있으며, $i$ 번째 나무의 위치는 $P_i$이다.

태영이는 카메라를 들고 파노라마 사진을 $Q$ 번 찍어, 이 아름다운 풍경을 담으려고 한다. 태영이는 이 사진에 점수를 매기려고 하는데, 사진의 점수는 사진을 찍은 위치로부터 각 나무까지의 거리 합이다. 이 때, 두 위치의 거리는 두 위치의 차의 절댓값으로 정의된다.

태영이가 찍은 사진에 대해서, 각 사진의 점수를 매겨주자.

입력

첫째 줄에는 나무의 개수 $N$과 태영이가 찍은 사진의 개수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄에는 나무의 위치 $P_1, P_2, \cdots, P_N$이 주어진다.

셋째 줄부터 $Q$개의 줄의 $i$ 번째 줄에는 태영이가 $i$ 번째로 사진을 찍은 위치 $X_i$가 주어진다.

출력

  $i$ 번째 줄에는 태영이가 $i$ 번째 찍은 사진의 점수를 한 줄에 하나씩 차례대로 출력한다.

문제 풀이

문제를 처음 풀 때 누적합을 사용해 특정 위치에서 모든 나무까지의 거리를 한번에 계산하고자 했다. 이렇게도 답은 나오지만 문제는 맨 왼쪽 나무보다 작은곳에서 찍으면 값이 제대로 계산되지 않았다. 이를 해결하려면 왼쪽 나무 오른쪽 나무를 나눠서 계산해야했다.

원래 아이디어 : 그림 바뀐 아이디어 : leftSum으로 왼쪽거리 합 + rightSum으로 오른쪽거리합, 왼쪽오른쪽개수는 파라매트릭서치로 찾고, 만약 첫 해결법과 같이 문제가 생기는 경우를 위해 맨 왼쪽보다 작으면 개수 0 반환하게 했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, Q, tree[];
	static long prefixSum[];
	static long sum;
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		tree = new int [N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			tree[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(tree);		
		
		prefixSum = new long[N+1];
		/*
		 * 처음아이디어 : 맨 왼쪽부터 진행해 나무 한그루씩 지나칠때마다 -2씩 되므로 이를 반영하여 누적합 -> 첫 O(N) 이후 쿼리마다 O(1)
		 * 			   -> 절댓값 계산 문제 발생
		 * 다음아이디어 : 왼쪽 오른쪽을 따로 해서 절댓값 오류까지 해결 ->  O(NlogN)
		 */
		for(int i=1; i<=N; i++) {
			prefixSum[i] = prefixSum[i-1] + tree[i-1];
		}
		
		for(int i=0; i<Q; i++) {
			int pos = Integer.parseInt(br.readLine());
			int left = findIdx(pos);
			long leftSum = (long) left * pos - prefixSum[left];
			long rightSum = (long) (prefixSum[N] - prefixSum[left]) - (long) pos * (N-left);
			
			sb.append(leftSum + rightSum).append("\n");
		}
						
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	private int findIdx(int pos) {
		int res = 0;
		int left = 0, right = tree.length-1;

        if(pos < tree[0]) return 0;

		while(left <= right) {
			int mid = left + (right-left) / 2;
			if(tree[mid] <= pos) {
				left = mid + 1;
				res = mid;
			}
			else {
				right = mid-1;
			}
		}
		return res+1; // 인덱스 0부턴데 개수반환해야하므로
	}
}