문제 소개
"시:분" 형식으로 표현된 24시간제 시간 지점들의 목록이 주어졌을 때, 목록에 있는 임의의 두 시간 지점 사이의 최소 분(minute) 차이를 구하는 문제입니다. 예를 들어 입력이 ["12:30", "15:17"]이라면 두 시점 사이의 차이는 167분이므로 결과는 167이 됩니다.
해결 접근 방법
하루는 총 24 × 60 = 1440분이므로, 모든 시간을 분 단위로 변환한 뒤 불리언 배열에 표시하고 순차적으로 탐색하면 효율적으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- 크기가 24 × 60 + 1인 불리언 배열 ok를 정의하고, 모든 값을 false로 초기화합니다.
- n := 입력 리스트 tp의 크기
- i를 0부터 n − 1까지 반복합니다.
- hr := 시간 문자열에서 시(hour) 부분
- min := 문자열에서 분(minute) 부분
- time := hr × 60 + min
- ok[time]이 이미 true라면 동일한 시간이 두 번 등장한 것이므로 0을 반환하고, 그렇지 않으면 ok[time]을 true로 설정합니다.
- last := 0, first := 무한대, ret := 무한대, prev := 음의 무한대로 초기화합니다.
- i를 0부터 24 × 60까지 순회하면서 ok[i]가 true인 경우 다음을 수행합니다.
- last := i와 last 중 최댓값
- first := i와 first 중 최솟값
- prev가 음의 무한대가 아니라면 ret := ret과 (last − prev) 중 최솟값
- prev := i
- 최종적으로 ret과 (24 × 60 + first − last) 중 최솟값을 반환합니다. 이 마지막 계산은 23:50과 00:10처럼 자정을 기준으로 시간이 넘어가는 경우의 차이까지 처리하기 위한 것입니다.
이 알고리즘의 시간 복잡도는 입력 처리에 O(n), 배열 순회에 O(1440)이 소요되므로 전체적으로 O(n + 1440)이며, 사실상 선형 시간에 동작합니다.
예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMinDifference(vector<string>& tp) {
vector <bool> ok(24 * 60 + 1, false);
int n = tp.size();
for(int i = 0; i < n; i++){
int hr = stoi(tp[i].substr(0, 2));
int min = stoi(tp[i].substr(3, 2));
int time = hr * 60 + min;
if(ok[time]) return 0;
ok[time] = true;
}
int last = 0;
int first = INT_MAX;
int ret = INT_MAX;
int prev = INT_MIN;
for(int i = 0; i <= 24 * 60; i++){
if(ok[i]){
last = max(i, last);
first = min(i, first);
if(prev != INT_MIN) ret = min(ret, last - prev);
prev = i;
}
}
return min(ret, 24 * 60 + first - last);
}
};
main(){
vector<string> v = {"12:30","15:17"};
Solution ob;
cout << (ob.findMinDifference(v));
}입력
["12:30","15:17"]
출력
167
마무리
이 문제의 핵심은 모든 시간을 분 단위 정수로 변환한 뒤, 하루의 총 분 수가 1440으로 제한되어 있다는 점을 활용해 불리언 배열로 중복을 검사하고 최소 간격을 찾는 것입니다. 특히 자정을 넘어가는 시간 차이를 별도로 계산해 비교하는 마지막 단계를 놓치지 않는 것이 중요합니다.