Q. 1860. 진기의 최고급 붕어빵(D3)

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이고, 만약 손님이 왔을 때 조건을 충족하지 않았을 경우 즉시 루프를 종료하게 구현했으므로 조금 더 빠르게 계산할 수 있게 코드를 작성했다.

 

현재 내가 푼 코드는 위 내용을 고려한 코드라, 지금은 더 개선할 방법이 떠오르지 않지만,나중에 생각나면 더 추가해야겠다.

---