문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 두 포인터
창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 다음과 같은 문제를 풀어야 한다.
지금까지 현우가 말한 모든 A와 모든 B를 짝짓는다. 이때, 각 쌍의 합 중에서 가장 큰 값을 작게 만들어라.
즉, 현재 라운드가 N 라운드이라고 하면, 현우가 창영이에게 말한 숫자는 a1, a2, ..., an 과 b1, b2, ..., bn이라고 할 수 있다. 이때, 각 숫자를 한 번씩 사용하여 (ai, bj)쌍을 n개 만들 수 있다. 이렇게 쌍을 모두 만들었을 때, ai+bj의 합 중 가장 큰 값을 가능한 작게 만들어야 한다.
입력
첫째 줄에 라운드의 수 N이 주어진다. (1 ≤ N ≤ 100000) 다음 N개의 줄에는 각 라운드에서 현우가 말한 숫자 A와 B가 주어진다. (1 ≤ A, B < 100)
출력
출력은 N줄이다. 각 줄은 해당하는 라운드에서 창영이가 말해야하는 값 (모든 쌍의 합의 최댓값의 최솟값) 이다.
풀이
각 숫자를 한 번씩 사용하여 (ai, bj)쌍을 n개 만들 수 있다. 이렇게 쌍을 모두 만들었을 때, ai+bj의 합 중 가장 큰 값을 가능한 작게 만들어야 한다.
A, B 수가 모두 N개 일 때 ai + bj의 합 중 가장 큰 값을 가능한 작게 만들기 위해서는 가장 작은 ai는 가장 큰 bj와 다음으로 작은 ai는 그 다음으로 큰 bj.. 이런 방식으로 짝을 지어야 한다.
예를 들어
1 4
7 8
4 5
일 때는
(1, 8), (4 , 5), (7, 4) 이렇게 짝을 지저야 최선이 된다.
그런데 N은 10만이고, 각 라운드마다의 값을 구해야 되는데, 단순히 모든 ai, bi를 돌면서 max를 구하는 방법은 시간 초과로 불가능하다.
새로운 ai, bi쌍이 추가되었을 때(새로운 라운드) max값을 구하기 위해서는 모든 쌍을 비교하는 방법밖에 없기 때문에 비교 횟수를 어떻게 줄일 수 있을까? -> ai, bi를 어떻게 줄일 수 있을까? 라는 생각을 해야 한다.
그래야 ai, bi는 어떠한 값이 들어가는 지를 보면, 100보다 작은 수이기 때문에, 100개를 유지한다면 O(200)으로 풀 수 있지 않을까? 라는 생각을 할 수 있다.
그러면 어떻게 ai, bi를 100개로 유지할 수 있을까? 문제는 같은 값이 들어왔을 때인데, 이를 카운트한다면, 해당 값을 묶어서 짝지어줄 수 있다.
예를 들어 1 ~ 100까지 각 수가 몇 개인지 카운트한 배열 A와 배열 B가 있을 때 어느 순간의 A와 B 배열은 다음과 같다고 해보자,
A
1 -> 2개
5 -> 3개
8 -> 1개
B
3 -> 3개
6 -> 1개
7 -> 2개
이때 A에서는 ind 1부터, B에서는 ind 7부터 시작한다. A에서 ind 1은 두 개, B에서 ind 7도 두 개이기 때문에 (A의 1 (2개), B의 7 (2개)) 이렇게 묶어서 짝을 짓는 것이다.
그러면, A의 cursor와 B의 cursor중 하나는 한 번 반복될 때마다 반드시 한 칸씩은 움직이기 때문에 O(200)을 유지하며, 각 라운드 별 최적해를 구할 수 있게 된다.
이 풀이의 시간 복잡도는 O(N * 200)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[] A = new int[101];
int[] B = new int[101];
StringBuilder sb = new StringBuilder();
for(int i=1; i<=N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int ai = Integer.parseInt(st.nextToken());
int bi = Integer.parseInt(st.nextToken());
A[ai] += 1;
B[bi] += 1;
int aCursor = 1;
int bCursor = 100;
int max = -1;
int cntPair = 0;
int[] cpA = copy(A);
int[] cpB = copy(B);
while(cntPair != i) {
if(cpA[aCursor] == 0 || cpB[bCursor] == 0) {
// A, B에서 0이 아닌 지점을 찾는다.
if(cpA[aCursor] == 0) {
aCursor += 1;
}
if(cpB[bCursor] == 0) {
bCursor -= 1;
}
continue;
}
//이제 a, b cursor가 0이 아닌 지점을 가리키고 있음
max = Math.max(max, aCursor + bCursor);
if(cpA[aCursor] <= cpB[bCursor]) {
cpB[bCursor] -= cpA[aCursor];
cntPair += cpA[aCursor];
cpA[aCursor] = 0;
aCursor += 1;
} else {
cpA[aCursor] -= cpB[bCursor];
cntPair += cpB[bCursor];
cpB[bCursor] = 0;
bCursor -= 1;
}
}
sb.append(max).append("\n");
}
System.out.println(sb.toString().trim());
}
static int[] copy(int[] arr) {
int[] result = new int[arr.length];
for(int i=0; i<arr.length; i++) {
result[i] = arr[i];
}
return result;
}
}