728x90
반응형
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분 단위의 상태 변화를 정확히 포착하는 것이 이 문제의 핵심이었습니다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
| [LeetCode] 402 Remove K Digits(Java) (0) | 2026.03.17 |
|---|---|
| [LeetCode] 1775 Closest Dessert Cost(Java) (0) | 2026.03.16 |
| [백준] BOJ 10808 알파벳 개수(Java) (0) | 2026.03.13 |
| [백준] BOJ 2309 일곱 난쟁이(Java) (0) | 2026.03.13 |
| [LeetCode] 427 Construct Quad Tree (1) | 2025.07.07 |