문제
철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.
N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.
철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.
민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.
K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.
입력
첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))
다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.
다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.
출력
K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.
예제 입력 1
10 7 5
2 5 3 7 8 4 9
4 1 1 3 8예제 출력 1
5
2
3
4
9예제 입출력으로 문제를 간단하게 설명해 보면 다음과 같다.
카드의 수는 1~10까지 있다.
민수가 가지고 있는 수는 2번째 줄에 7개
철수가 내는 카드는 3번째 줄에 5개이다.
민수는 철수가 내는 카드보다 큰 숫자를 내면 된다.
이때, 자기가 가지고 있는 수 중 가장 작은 카드를 내면 된다.
step 1. 철수가 4를 냈음.
민수는 4보다 크며, 가진것중에 제일 작은 수 5를 내면 된다.
철수가 가진 카드목록 (2 3 7 8 4 9)
step 2. 철수가 1을 냈음.
민수는 1보다 크며, 가진것중에 제일 작은 수 2를 내면 된다.
철수가 가진 카드목록 (3 7 8 4 9)
step 3. 철수가 1을 냈음.
민수는 1보다 크며, 가진것중에 제일 작은 수 3를 내면 된다.
철수가 가진 카드목록 (7 8 4 9)
step 4. 철수가 3을 냈음.
민수는 3보다 크며, 가진것중에 제일 작은 수 4를 내면 된다.
철수가 가진 카드목록 (3 7 8 9)
step 5. 철수가 8을 냈음.
민수는 8보다 크며, 가진것중에 제일 작은 수 9를 내면 된다.
철수가 가진 카드목록 (3 7 8)
따라서 result = 5,2,3,4,9풀이
일단 나는 알고리즘 분류에 있는
- 자료 구조
- 이분 탐색
- 분리 집합여기 안에 있는 알고리즘들로 풀지 않았다.
알고리즘이라고 하긴 그렇지만 Bucket으로 풀었다.
-
N <= 4_000_000 이라고 했으니까,
1 ~ 4_000_000 까지의 num 배열을 선언을 한다. -
sqrt(4_000_000) = 2000 인 bucket배열 2000개도 선언한다.
1번 버킷은 0 ~ 1999 까지의 num배열을 가르킨다.
2번 버킷은 2000 ~ 3999 까지의 num배열을 가르킨다.
3번 버킷은 4000 ~ 5999 까지의 num배열을 가르킨다.
...
2000번 버킷은 3_998_000 ~ 3_999_999 까지의 배열을 가르킨다.
(2001번까지 선언해서 4_000_000까지 측정했는데 어떤 접근 방식인지 알기 쉽게 설명하려고 2000번까지라 했다.)
민수는 철수가 낸 카드보다 큰 카드를 내야한다.
(민수가 내는 카드를 x라고 가정)
그러면 2가지 step을 따르면 된다.
step 1. (x + 1)는 xBucket에 있다.
xBucket를 num배열의 idx로 바꾸고 마지막 인덱스 + 1은
((x / 2000) + 1 ) 2000 이다.
그러면 (x + 1) ~ ((x / 2000) + 1 ) 2000 까지만 찾아보면 된다.
말이 어려워 보이는데 그냥 x + 1이 있는 버킷만 다 찾는다는거다.
step 2. xBucket + 1,2,3,4.... 모두 확인 해보면 된다.
그렇지만 각 버킷안에 num배열 2000개 모두 확인 할 필요는 없다. bucket배열은 버킷 범위 내에 num이 몇개있는지 알고 있으니까 bucket[a] = 0 이라면 그 버킷에는 num이 하나도 없다는거니까 그 다음 버킷을 확인하면 된다.
버킷안에 있다면 그 버킷안에있는 num배열 모두 탐색하면 됨.
solution code
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuffer sb = new StringBuffer();
static StringTokenizer st;
static final int SQRT = 2000;
static int n, m, k;
static int[] bucket = new int[2001];
static boolean[] num = new boolean[4_002_001];
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
int x = Integer.parseInt(st.nextToken());
num[x] = true;
bucket[x / SQRT]++;
}
st = new StringTokenizer(br.readLine());
out:for (int i = 0; i < k; i++) {
int tar = Integer.parseInt(st.nextToken());
int idx = tar / SQRT;
// x ~ x버킷
if(bucket[idx] != 0){
for (int x = tar + 1; x < (idx + 1) * SQRT; x++) {
if(num[x]){
num[x] = false;
bucket[x / SQRT]--;
sb.append(x).append("\n");
continue out;
}
}
}
//x버킷 + 1 ~ 나머지
idx++;
while (bucket[idx] == 0) idx++;
for (int x = idx * SQRT; x < (idx + 1) * SQRT; x++) {
if(num[x]){
num[x] = false;
bucket[x / SQRT]--;
sb.append(x).append("\n");
continue out;
}
}
}
System.out.println(sb);
}
}
