문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 수학
입력
출력
각 우선권 승객이 언제 자리에 앉을 수 있는지 시간 𝑚개를 출력합니다.
풀이
각 우선권 승객이 언제 자리에 앉을 수 있는지 시간 m개를 출력해야 한다.
우선권 승객이 탔을 때 경우는 다음과 같다.
- 빈자리가 있는 경우 -> 이 경우는 빈자리에 앉으면 된다.
- 빈자리가 없는 경우 -> 일반 승객이 핸드폰에서 눈을 때는 시각인지 확인한다.
간단한 문제 같지만, n과m은 최대 10만이기 때문에 O(n * m) 풀이가 불가능하다.
그래서 핸드폰에서 눈을 때는 시각을 미리 배열에 저장해 놓는 방식으로 풀어야 한다.
눈을 때는 시각은 a의 배수이기 때문에 index가 최대 20만인 배열에 +해준다.
a가 전부 다른 수라면 20만 배열을 채우는 시간 복잡도는 O(log20만)이지만,
만약 모든 a가 1이라면 O(20만*10만)이 된다. 그래서 중복 처리를 해줘야 한다.
예를 들어 a가 1인 승객이 5명이라면 1의 배수에 5씩 더 해주는 것이다.
그러면 O(log20만) 이하를 유지해 줄 수 있다.
눈을 때는 승객의 주기를 배열에 다 저장해 놓았다면,
1부터 20만까지 반복해주면서, 현재 시각에 우선권 승객이 몇 명인지 체크해 주며 빈자리에 앉을 수 있는지 없는지를 체크해 주면 된다.
각 시각(1~20만)에서 경우는 다음과 같다.
- 빈자리가 있는 경우 -> 빈자리에 앉는다.
- 아직도 서있는 우선권 승객이 있다면 주기(눈을 때는 승객의 주기)를 확인한다. - 빈자리가 없는 경우 -> 주기를 확인한다.
주기를 확인한다.
현재 주기에 승객이 핸드폰에서 눈을 때는 경우가 있다면 그 수를 빈자리 수의 count 해준다.
그리고 우선권 승객이 그 빈자리를 앉는다.
여기서 중요한 점은 현재 시각부터 +주기를 하면서 최대 20만까지 자리를 비켜준 일반 승객의 주기를 없애줘야 한다.
예를 들어 시각 3에 주기 3인 승객 2명, 주기 1인 승객 3명이 있다면 현재 빈자리는 5개가 되고, 이후에 6 -> 9 -> 12 ... 주기와 4 -> 5 -> 6 -> 7 ... 주기의 승객을 없애줘야 한다.
이 경우도 채워줬을 때의 시간 복잡도와 같기 때문에 최대 O(log20만)이 된다.
주기를 확인하고 나서 아직도 우선권 승객이 남아있다면, 다음 시각으로 넘겨준다.
예제 입력 1로 답을 구하는 과정을 보겠다.
3 2
3 1 2
2 4
다음은 주기 배열이다.
ind 1: {주기: 1, 승객 수: 1} 총 1명
ind 2: {주기: 1, 승객 수: 1}, {주기: 2, 승객 수: 1} 총 2명
ind 3: {주기: 1, 승객 수: 1}, {주기; 3, 승객 수: 1} 총 2명
ind 4: {주기: 1, 승객 수: 1}, {주기: 2, 승객 수: 1} 총 2명
첫 번째 우선권 승객은 시각 2에 탑승했다.
빈자리가 없기 때문에 주기를 확인한다.
ind 2에는 총 2명의 승객이 핸드폰에 눈을 때고, 빈자리 2개가 생긴다.
그래서 2시각에 앉을 수 있고, 빈자리는 1이 된다.
여기서 다음 주기를 삭제해 준다. (3 -> 4 -> 5...), (4 -> 6 -> 8...)
그래서
ind 3: {주기; 3, 승객 수: 1} 총 1명
ind 4: 총 0명이 된다.
두 번째 우선권 승객이 시각 4에 탑승했을 때는 빈자리가 하나 있기 때문에
4시각에 앉게 된다.
그래서 최종 답은 2 4가 되는 것이다.
이 풀이의 시간 복잡도는 O(20만*log20만)이다.
소스 코드
import java.io.*;
import java.util.*;
class Info {
int v; //총 몇 명
HashMap<Integer, Integer> map;
Info(int v) {
this.v = v;
map = new HashMap<>();
}
}
public class Main {
static int n,m;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
Info[] info = new Info[200001];
int[] num = new int[100001];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
num[Integer.parseInt(st2.nextToken())] += 1;
}
for(int i=1; i<=100000; i++) {
if(num[i] > 0) {
for(int j=i; j<=200000; j+=i) {
if(info[j] == null) {
info[j] = new Info(0);
}
info[j].v += num[i];
info[j].map.put(i, num[i]);
}
}
}
StringTokenizer st3 = new StringTokenizer(br.readLine());
int[] priPass = new int[200001]; //우선 승객
for(int i=0; i<m; i++) {
priPass[Integer.parseInt(st3.nextToken())] += 1;
}
int vCnt = 0; //빈자리
StringBuilder sb = new StringBuilder();
for(int i=1; i<=200000; i++) {
if(priPass[i] > 0) {
if(vCnt > 0) {
//빈자리가 있으면
int len = priPass[i];
for(int j=1; j<=len; j++) {
if(vCnt == 0 || priPass[i] == 0) {
break;
}
priPass[i] -= 1;
vCnt -= 1;
sb.append(i).append(" ");
}
}
if(priPass[i] > 0) {
//아직도 앉지 못한 우선 승객이 있다면 주기를 확인한다.
if(info[i] != null && info[i].v > 0) {
//주기가 있다면
vCnt += info[i].v;
int len = priPass[i];
for(int j=1; j<=len; j++) {
if(vCnt == 0 || priPass[i] == 0) {
break;
}
priPass[i] -= 1;
vCnt -= 1;
sb.append(i).append(" ");
}
//주기를 삭제해 준다.
for(Map.Entry<Integer, Integer> entry : info[i].map.entrySet()) {
for(int j=i + entry.getKey(); j<=200000; j+=entry.getKey()) {
info[j].v -= entry.getValue();
info[j].map.remove(entry.getKey());
}
}
}
}
if(priPass[i] > 0) {
//우선권 승객이 남아있다면 다음으로 이월
priPass[i + 1] += priPass[i];
}
}
}
System.out.println(sb.toString().trim());
}
}