[백준] BOJ 2979 트럭 주차(Java)

1. 문제 설명

문제 링크: 백준 2979번 - 트럭 주차

요약: 세 대의 트럭이 주차된 시간대에 따라 주차 요금을 계산하는 문제입니다. 주차된 트럭의 대수(1대, 2대, 3대)에 따라 한 대당 부과되는 요금이 달라지며, 각 트럭의 입차 시간과 출차 시간이 주어질 때 총 주차 요금을 구해야 합니다.

2. 핵심 아이디어

이 문제를 처음 봤을때 인터벌 그래프 문제로 생각하고 봤는데 구간도 노드도 작아 시뮬레이션으로 접근했습니다. 핵심은 특정 시각에 주차장에 차가 몇 대 있는지 파악하는 것입니다.

• 요금 처리: 1대일 때 A, 2대일 때 B, 3대일 때 C원이며 이는 '한 대당' 요금입니다. 코드에서는 계산의 편의를 위해 **(요금 * 대수)**를 미리 계산하여 배열에 저장합니다.
• 시점 관리: 각 트럭의 입차 시간과 출차 시간을 기록합니다.
• 시뮬레이션: 가장 빠른 입차 시간부터 마지막 출차 시간까지 1분 단위로 시간을 흐르게 하면서, 해당 시각에 들어온 차와 나간 차를 체크하여 현재 주차된 차량 수(cnt)를 갱신합니다.

3. 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] price = new int[3], inTime = new int[3], outTime = new int[3];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 3; i++) {
            // 대수별 총 요금을 미리 계산 (i+1은 차량 대수)
            price[i] = Integer.valueOf(st.nextToken()) * (i + 1);
        }
        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            inTime[i] = Integer.valueOf(st.nextToken());
            outTime[i] = Integer.valueOf(st.nextToken());
        }

        // 시간 순서대로 이벤트를 처리하기 위해 정렬
        Arrays.sort(inTime);
        Arrays.sort(outTime);
        int inIdx = 0, outIdx = 0, cnt = 0, ret = 0;

        // 첫 입차 시각부터 마지막 출차 시각까지 1분 단위로 탐색
        for (int i = inTime[0]; i < outTime[2]; i++) {
            // 현재 시각(i)에 입차한 차량이 있다면 cnt 증가
            while (inIdx < 3 && inTime[inIdx] <= i) {
                cnt++;
                inIdx++;
            }
            // 현재 시각(i)에 출차한 차량이 있다면 cnt 감소
            while (outIdx < 3 && outTime[outIdx] <= i) {
                cnt--;
                outIdx++;
            }
            // 주차된 차량이 있다면 해당 대수에 맞는 미리 계산된 요금 합산
            if (cnt != 0) {
                ret += price[cnt - 1];
            }
        }

        System.out.println(ret);
    }
}

4. 코드 포인트 해설

• price[i] = 요금 * (i + 1): 1대일 때(A1), 2대일 때(B2), 3대일 때(C*3)의 합산 요금을 미리 구해두어 조건분기 없이 인덱스 접근만으로 요금을 계산했습니다.
• 투 포인터 활용: inTime과 outTime을 정렬한 뒤 inIdx, outIdx를 사용하여 현재 시간 i에 발생하는 입/출차 이벤트를 효율적으로 처리했습니다.
• while 루프: 같은 시각에 여러 대가 들어오거나 나가는 경우를 대비하여 if 대신 while을 사용하여 정확하게 cnt를 갱신합니다.

5. 성능 및 복잡도

• 시간 복잡도: 트럭의 수가 3대로 고정되어 있습니다. 전체 시간 범위를 $T$라고 할 때 **$O(T)$**의 복잡도를 가지며, $T$는 최대 100이므로 매우 효율적입니다.
• 공간 복잡도: 입력 데이터를 저장하는 고정 크기 배열 외에 추가 메모리를 거의 사용하지 않으므로 **$O(1)$**입니다.

6. 마치며

단순히 시간 배열을 100까지 만들어 체크하는 방법도 있지만, 위와 같이 정렬과 인덱스 포인터를 활용한 방식은 시간 범위가 매우 커지는 상황에서도 유연하게 대응할 수 있는 좋은 접근법입니다. 1분 단위의 상태 변화를 정확히 포착하는 것이 이 문제의 핵심이었습니다.