이 글에서는 주어진 네 개의 숫자로 만들 수 있는 최대 시간을 구하는 프로그램을 C++로 작성하는 방법을 소개합니다.
네 개의 숫자로 이루어진 배열이 주어졌을 때, 이 숫자들을 모두 정확히 한 번씩 사용하여 24시간 형식(HH:MM)으로 나타낼 수 있는 가장 늦은 시간을 찾는 것이 목표입니다. 만약 유효한 시간을 만드는 것이 불가능하다면 "-1"을 반환해야 합니다.
문제 접근 방법
가장 효율적인 해결책은 그리디(Greedy) 기법과 빈도 맵(Frequency Map)을 함께 활용하는 것입니다. 시간의 각 자리에 올 수 있는 최댓값부터 내림차순으로 살펴보고, 아직 사용하지 않은 숫자가 있으면 그 자리에 배치하는 방식입니다.
24시간 형식에서 각 자리의 허용 범위는 다음과 같습니다.
- 시(hour)의 십의 자리: 0 ~ 2
- 시(hour)의 일의 자리: 십의 자리가 2라면 0 ~ 3, 그렇지 않으면 0 ~ 9
- 분(minute)의 십의 자리: 0 ~ 5
- 분(minute)의 일의 자리: 0 ~ 9
예를 들어 배열이 {0, 0, 0, 9}로 주어진다면, 만들 수 있는 가장 늦은 시간은 09:00입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 업데이트된 빈도 맵을 반환하는 함수
map<int, int> getFrequencyMap(int arr[], int n) {
map<int, int> hashMap;
for (int i = 0; i < n; i++) {
hashMap[arr[i]]++;
}
return hashMap;
}
// 빈도 맵에 해당 숫자가 존재하는지 확인하는 함수
bool hasDigit(map<int, int>* hashMap, int digit) {
if ((*hashMap)[digit]) {
(*hashMap)[digit]--;
return true;
}
return false;
}
// 24시간 형식으로 만들 수 있는 최대 시간을 반환하는 함수
string getMaxtime_value(int arr[], int n) {
map<int, int> hashMap = getFrequencyMap(arr, n);
int i;
bool flag;
string time_value = "";
flag = false;
for (i = 2; i >= 0; i--) {
if (hasDigit(&hashMap, i)) {
flag = true;
time_value += (char)i + 48;
break;
}
}
if (!flag)
return "-1";
flag = false;
if (time_value[0] == '2') {
for (i = 3; i >= 0; i--) {
if (hasDigit(&hashMap, i)) {
flag = true;
time_value += (char)i + 48;
break;
}
}
}
else {
for (i = 9; i >= 0; i--) {
if (hasDigit(&hashMap, i)) {
flag = true;
time_value += (char)i + 48;
break;
}
}
}
if (!flag)
return "-1";
time_value += ":";
flag = false;
for (i = 5; i >= 0; i--) {
if (hasDigit(&hashMap, i)) {
flag = true;
time_value += (char)i + 48;
break;
}
}
if (!flag)
return "-1";
flag = false;
for (i = 9; i >= 0; i--) {
if (hasDigit(&hashMap, i)) {
flag = true;
time_value += (char)i + 48;
break;
}
}
if (!flag)
return "-1";
return time_value;
}
int main() {
int arr[] = { 0, 0, 0, 9 };
int n = sizeof(arr) / sizeof(int);
cout << (getMaxtime_value(arr, n));
return 0;
}
실행 결과
09:00
코드 동작 원리
- getFrequencyMap: 배열을 한 번 순회하며 각 숫자의 등장 횟수를 map에 저장합니다.
- hasDigit: 특정 숫자가 아직 남아 있는지 확인하고, 남아 있다면 개수를 하나 차감한 뒤 true를 반환합니다. 이를 통해 같은 숫자를 중복해서 사용하는 실수를 방지할 수 있습니다.
- getMaxtime_value: 시의 십의 자리(2→0), 시의 일의 자리(앞자리가 2면 3→0, 아니면 9→0), 분의 십의 자리(5→0), 분의 일의 자리(9→0) 순서로 배치 가능한 가장 큰 숫자를 찾아 이어 붙입니다.
- 네 자리 중 어느 하나라도 배치에 실패하면 즉시 "-1"을 반환하여 유효한 시간을 만들 수 없음을 알립니다.
시간 복잡도
배열 순회와 각 자리별 탐색은 최대 10번의 반복으로 상수 시간 안에 처리되므로, 전체 시간 복잡도는 O(n)입니다. 또한 숫자의 종류가 0~9 사이로 제한되므로 공간 복잡도 역시 O(1)입니다.