백준 안테나(18310)

안테나

1. 힌트

1) 단순하게 구현하면 모든 집에 대해서 나머지 집 까지의 거리의 합을 계산하게 할 수 있습니다. 이렇게 하면 $O(N^2)$이 됩니다.

2) 어떤 집에 안테나를 설치하기로 했는데 그 집에서 왼편에 있는 집의 수가 오른편에 있는 집의 수보다 많다면 여기에 설치하지 않고 왼쪽으로 옮기는 것이 무조건 이득입니다.

3) 주어진 수열을 정렬해 왼쪽에 있는 집의 개수와 오른쪽에 있는 집의 개수가 동일한 지점을 찾습니다. 당연히 $\frac{N}{2}$번째 위치가 되는데 $N$이 짝수일 경우 답이 두개가 되므로 $\frac{N-1}{2}$이 정답입니다.

2. 접근

1) 그림으로 그려볼 수 있을까?

맨 왼쪽에 있는 집과 맨 오른쪽에 있는 집으로 직접 해보겠습니다. 만약 $1$의 위치에 있는 집을 선택한다면 두 집 사이의 거리는 $0 + 8$입니다.
$5$의 위치에 있는 집을 선택한다면 $4 + 4$입니다
$7$의 위치에 있는 집을 선택한다면 $6 + 2$입니다
$9$의 위치에 있는 집을 선택한다면 $8 + 0$입니다
이처럼 어느 집을 선택하더라도 맨 왼쪽에 있는 집과 맨 오른쪽에 있는 집과의 거리는 일정합니다. 이 말은 이보다 더 낮아질 수는 없다는 것을 뜻합니다. 더 커질 수는 있습니다 $5$와 $7$의 입장에서 바깥에 있는 $1$을 선택한다면 $5$와 $7$사이의 거리는 $2$인데 더 늘어나게 됩니다.

따라서 맨 가운데에 있는 집을 고르는 것이 가장 최적해입니다. 이를 위해서 정렬해줍니다.

2) 수식으로 표현할 수 있을까?

다른 방법으로 문제를 풀 수도 있습니다. $C[x]$는 $x$위치에 있는 집의 개수를 저장합니다. $P[x]$는 $x$위치에 있는 집의 좌표값의 합을 저장합니다.
어떤 집에 안테나를 선택했을 때, 모든 집까지의 거리는
왼편 : $x\displaystyle\sum_{k=0}^{x-1}C[k]\ \ -\displaystyle\sum_{k=0}^{x-1}P[k]$로 구할 수 있고
오른편 : $\displaystyle\sum_{k=x+1}^{100000}P[k] \ \ - x\displaystyle\sum_{k=x+1}^{100000}C[k]$으로 구할 수 있습니다.
$C$와 $P$는 누적 합 배열을 이용해 간단히 구현할 수 있습니다.

3. 구현

누적 합 배열을 이용하는 풀이입니다.

public class Main {
	
	static long sum(long[] S, int i, int j) {
		if (i > j) return 0;
		return S[j] - (i == 0 ? 0 : S[i - 1]);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] S = new int[N];
		// P[x] = x위치 이하 좌표값의 합 C[x] = x위치 이하 좌표의 개수 합      
		long[] P = new long[100001]; long[] C = new long[100001];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		for (int x : S) { P[x] += x; C[x]++; }
		for (int i = 1; i <= 100000; i++) { 
			P[i] += P[i - 1]; C[i] += C[i - 1];
		}
		long min = Long.MAX_VALUE;
		int ret = 100000;
		for (int x : S) {
			long sum = sum(C, 0, x - 1) * x - sum(P, 0, x - 1) +
			sum(P, x + 1, 100000) - sum(C, x + 1, 100000) * x;
			if (min >= sum) {
				if (min > sum || (min == sum && ret > x)) ret = x;
				min = sum;
			}
		}
		System.out.println(ret);
	}

}

1) 시간 복잡도

정렬해서 가운데 값을 찾는 풀이의 시간 복잡도는 당연히 정렬이 지배하므로 $O(NlgN)$입니다. 이 풀이는 정렬하지 않아도 되므로 $O(N)$입니다.

2) 테스트 케이스