(Java) SWEA 1860. 진기의 최고급 붕어빵 풀이(2023-02-24)

1. 문제 조건 분석하기

진기가 M초마다 K개씩 만드는 붕어빵을 N명에게 판매.

N명은 입력된 숫자의 시간에 도착하며 기다리지 않고 받아갈 수 있다면 Possible, 불가능하면 Impossible 출력할 것.

 

2. 아이디어 

1)  카운팅 배열을 만든 후 사람이 들어오는 시간을 index로 하여 max시간까지 만든 붕어빵을 값으로 더한다. 그리고 누적합 시킨다. 그 후, 입력값을 돌며 해당 시간에 들어온 사람만큼 붕어빵을 빼준다.( 이 때,  배열에서 끝까지 빼주지 않으면 앞에서 사간 붕어빵이 그 시간 이후에 반영되지 않으므로 주의해야 한다.) => 사람이 들어온 시간을 정렬시켜 시간 순으로 빼주고 뺄 때마다 붕어빵 개수가 0보다 작아졌는지 확인후 작아졌으면 Impossible을 다 돌고도 문제가 없었으면 Possible을 출력하도록 한다.

 

2) 위의 1)방법을 처음에 구상했다가 누적합 카운팅 배열에서 사람이 붕어빵을 사갈 때마다 해당 배열의 끝까지를 돌며 1씩 빼는 것보다 더 효율적인 방법은 없을까 고민했다. 그래서 떠올린 방법은, 붕어빵의 개수를 배열에 넣지 말고 sum이라는 변수에 넣고 사람이 들어온 시간을 돌면서 sum에서 붕어빵을 1개씩 빼주고, 그 시간이 추가로 붕어빵이 나올 시간이거나 혹은 붕어빵이 나온 후의 시간이라면 또 새로 구워진 붕어빵을 +하는 방식을 구상해보았다.

 

 

3. 구현

이 때 while문의 조건이나 time을 고려하는 것이 상당히 헷갈렸는데 손님이 도착한 시간에는 과거에 만든 붕어빵은 있지만 이후에 만든 붕어빵은 없다 ! 는 것을 명심하면 이해가 쉽다.

예를들어 3초마다 붕어빵이 나오고 5초에 붕어빵을 사러온 손님이 있을 때 이 손님은 그 다음인 6초에 나오는 붕어빵이 아닌 3초에 만들어놨던 붕어빵을 사게 되는 것이다. 이렇게 붕어빵이 나오는 시간 사이에 도착하면 그 앞 time까지의 sum을 고려해야 한다. 따라서, sec를 모두 돌며 붕어빵을 사러 온 손님의 시간이 현재 설정된 time(가장 최근 붕어빵이 나온 시간)보다 크거나 같을 때만 붕어빵 전체 개수에서 1을 빼줘야 한다.

public class Solution_1860진기붕어빵 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
        //테스트 케이스 수 입력
		int T = Integer.parseInt(br.readLine());
		//테스트 케이스만큼 for문 반복
		for (int t = 1; t <= T; t++) {
        	//결과값의 기본 값의 "Possible" 중간에 Impossible로 바뀌지 않는다면 그대로 출력
			String result = "Possible";
			//N,M,K값 입력받기
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); //손님의 수
			int M = Integer.parseInt(st.nextToken()); //붕어빵이 나오는 시간단위
			int K = Integer.parseInt(st.nextToken()); //한 타임에 붕어빵이 나오는 개수

			//손님이 오는 시간을 배열로 입력받기
			int[] sec = new int[N];
			st = new StringTokenizer(br.readLine());
			int k = 0;
			while (st.hasMoreTokens()) {
				sec[k] = Integer.parseInt(st.nextToken());
				k++;
			}
			//손님이 오는 시간 오름차순으로 정렬
			Arrays.sort(sec);

			int sum = 0; //현재 붕어빵의 개수
			int time = 0; //시간  M 2M 3M ... (가장 최근 붕어빵이 나온 시간)
			int idx = 0; // sec의 index를 어디까지 돌았는지 기억하기 위한 변수
			
            //손님 도착시간 배열의 index를 넘어가지 않으면서,
            //붕어빵 나오는 시간이 제일 늦은 손님이 도착한 시간을 넘지않는 동안 반복
           	//(제일 늦은 손님이 오고 나면 그 후엔 붕어빵 개수를 체크할 필요가 없으므로)
			while (idx < N && time <= sec[N - 1]) {
            	//다음 붕어빵이 나올 시간이 sec배열에서 내가 보고있는 값보다 작거나 같다면
                //시간 추가, 그 시간에 구워진 붕어빵도 추가.
				while(time+M<=sec[idx]) {
					time += M;
					sum += K;
				}
				//가장 최근 붕어빵이 나온시간보다 현재손님이 온시간이 더 늦거나 같다면
                //붕어빵 1개 팔리고 다음 손님 확인(sum--/idx++)
				if (time <= sec[idx] && time+M > sec[idx])  {
					sum--;
					idx++;
					
				}
                //한 손님을 다 보고 나서 sum<0이면 붕어빵이 부족했다는 뜻이므로 
                //result값 바꾸고 종료
				if (sum < 0) {
					result = "Impossible";
					break;
				}
			}
			//출력
			System.out.printf("#%d %s \n", t, result);

		}

	}

}