Q. 1860. 진기의 최고급 붕어빵(D3)
0. 문제
D3 난이도의 문제이고, 구현 문제라고 생각된다.
N, M, K가 주어진다.
N은 붕어빵을 먹으려는 사람의 수 이고, M초에 K개의 붕어빵을 만들 수 있다.
한 손님은 한 개의 붕어빵을 가져 간다고 하면,
모든 손님들에게 기다리는 시간없이 붕어빵을 제공할 수 있는지 판별하는 프로그램을 작성하라.
1. 풀이
1) 손님들이 오는 순서가 차례대로 주어지지 않으므로 먼저 입력을 받은 뒤 정렬을 한다.
2) 그리고 손님들을 받으면서, 만약 현재 붕어빵이 없을 경우
손님의 시간 이하인 K 배수만큼 시간을 더하고, 붕어빵을 만들어서 손님에게 줄 수 있는지 판별한다.
3) 손님에게 줄 수 없을경우 즉시 루프를 종료한다.
시간을 줄이기 위해 손님이 온 시간에 만약 붕어빵이 있을 경우 2)번 동작을 하지 않고 바로 다음 손님을 받았다.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Solution {
static BufferedReader br;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[] BreadArr;
static int N, M, K;
public static void input() 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());
BreadArr = new int[N];
for (int i = 0; i < N; i++) {
BreadArr[i] = Integer.parseInt(st.nextToken());
}
}
public static void pro(int tc) {
boolean res = true;
Arrays.sort(BreadArr);
int curTime = 0;
int curBreadCnt = 0;
for (int i = 0; i < N; i++) {
if (curBreadCnt > 0) {
curBreadCnt--;
continue;
}
if (curTime < BreadArr[i]) {
int time = (BreadArr[i] - curTime) / M;
curTime += time * M;
curBreadCnt += time * K;
}
if (curBreadCnt > 0) {
curBreadCnt--;
} else {
res = false;
break;
}
}
sb.append(String.format("#%d ", tc));
if (res) sb.append("Possible");
else sb.append("Impossible");
sb.append('\n');
}
public static void main(String[] args) throws Exception {
//br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
input();
pro(tc);
}
System.out.println(sb);
}
}2. 시간복잡도 계산
0) 1 ≤ N, M, K ≤ 100 , 0 <= 손님의 도착 시간(A) <= 11111
1) 손님의 도착 시간 저장 - O(N)
2) 손님 배열 정렬 - O(NlogN)
3) 풀이 1번 - O(N)
위 세 연산은 연관성이 없으므로 덧셈으로 시간복잡도를 계산하게 된다.
따라서 시간복잡도는 O(N log N)이고, 시간제한은 2초이므로
1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.
3. 성능 개선 방안
1) 손님을 정렬해두고 만약 모든 시간 마다 붕어빵의 수를 미리 계산해두고, 손님을 받았다면 O(N^2)이 걸렸을 것 이다.
하지만 손님이 도착했을 때 붕어빵이 만약 없다면, 손님이 도착하는 시간 전 까지 붕어빵을 만드는 식으로 해서 손님이 O(N)으로 좀 더 빠르게 동작하도록 변경했다.
2) 손님의 수가 최대 100이고, 만약 손님이 왔을 때 조건을 충족하지 않았을 경우 즉시 루프를 종료하게 구현했으므로 조금 더 빠르게 계산할 수 있게 코드를 작성했다.
현재 내가 푼 코드는 위 내용을 고려한 코드라, 지금은 더 개선할 방법이 떠오르지 않지만,나중에 생각나면 더 추가해야겠다.