문제 개요
"HH:MM" 형식으로 표현된 시간이 주어졌을 때, 현재 시간에 사용된 숫자들을 재활용하여 만들 수 있는 다음으로 가까운 시간을 구하는 문제입니다. 이때 각 숫자는 무제한으로 재사용할 수 있습니다.
예를 들어 입력이 "19:34"라면 출력은 "19:39"가 됩니다. 숫자 1, 9, 3, 4를 조합하여 만들 수 있는 시간 중 현재보다 가장 가까운 미래 시각이 19:39이기 때문입니다. 참고로 "19:33"은 겉보기에는 더 가까워 보이지만, 실제로는 자정을 지나 23시간 59분 후에야 도래하는 시간이므로 정답이 될 수 없습니다.
풀이 접근 방법
이 문제는 브루트 포스(완전 탐색) 방식으로 해결할 수 있습니다. 먼저 시간을 분 단위로 변환하는 eval() 함수를 정의합니다.
- eval(x) : 문자열 x를 매개변수로 받습니다.
- a := x[0]을 문자열로 변환한 뒤 x[1]을 이어 붙입니다. (시(hour) 부분)
- b := x[2]를 문자열로 변환한 뒤 x[3]을 이어 붙입니다. (분(minute) 부분)
- a를 정수로 변환한 값 × 60 + b를 정수로 변환한 값을 반환합니다.
메인 메서드(nextClosestTime)에서는 다음 과정을 수행합니다.
- 결과를 담을 ret(빈 문자열), 임시 문자열 temp, 최소 시간 차이 diff(무한대로 초기화)를 준비합니다.
- 배열 time에 입력 문자열 t의 0, 1, 3, 4번째 문자, 즉 콜론(:)을 제외한 네 개의 숫자를 저장합니다.
- n := time의 크기로 설정하고, 원본 시간 문자열 src를 생성합니다.
- 네 개의 중첩 반복문(i, j, k, l)을 사용해 만들 수 있는 모든 시:분 조합을 탐색합니다.
- temp1 := time[i] + time[j] (시), temp2 := time[k] + time[l] (분)
- 시가 23을 초과하거나 분이 59를 초과하면 유효하지 않으므로 해당 조합은 건너뜁니다.
- 생성된 시간이 원본(src)과 같으면 건너뜁니다.
- newDiff := eval(temp) − eval(src)로 시간 차이를 계산하고, 값이 음수라면 하루(60 × 24 = 1440분)를 더해 보정합니다.
- newDiff가 기존 diff보다 작으면 diff와 ret을 갱신합니다.
- 모든 탐색이 끝난 후 ret이 비어 있다면 원본 시간 t를, 그렇지 않으면 ret을 반환합니다.
구현 예제
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int eval(string x){
string a = to_string(x[0]);
a += x[1];
string b = to_string(x[2]);
b += x[3];
return stoi(a) * 60 + stoi(b);
}
string nextClosestTime(string t) {
string ret = "";
string temp = "";
int diff = INT_MAX;
vector<char> time;
time.push_back(t[0]);
time.push_back(t[1]);
time.push_back(t[3]);
time.push_back(t[4]);
int n = time.size();
string src = "";
string temp1 = "";
string temp2 = "";
for (int i = 0; i < n; i++)
src += time[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++) {
temp1 = time[i];
temp1 += time[j];
temp2 = time[k];
temp2 += time[l];
if (stoi(temp1) > 23 || stoi(temp2) > 59)
continue;
temp = temp1 + temp2;
if (temp == src)
continue;
int newDiff = eval(temp) - eval(src);
if (newDiff < 0)
newDiff += (60 * 24);
if (newDiff < diff) {
diff = newDiff;
ret = temp1 + ":" + temp2;
}
}
}
}
}
return ret.size() == 0 ? t : ret;
}
};
main(){
Solution ob;
cout<<(ob.nextClosestTime("19:34"));
}입력
"19:34"
출력
19:39