"hh:mm" 형식의 24시간제 시간 문자열이 주어졌을 때, 해당 문자열에 포함된 숫자들을 재사용하여 만들 수 있는 다음으로 가장 가까운 시간을 찾는 문제입니다. 여기서 중요한 점은 주어진 숫자를 원하는 만큼 여러 번 반복해서 사용할 수 있다는 것입니다.
예를 들어 입력이 s = "03:15"라면, 출력은 03:30이 됩니다. 주어진 숫자(0, 3, 1, 5)만으로 만들 수 있는 시간 중 03:15 바로 다음에 오는 시간이 03:30이기 때문입니다.
문제 해결 접근 방법
이 문제는 백트래킹(backtracking) 기법을 사용하여 해결할 수 있습니다. 전체 알고리즘은 다음과 같은 단계로 진행됩니다.
- 주어진 문자열에서 시와 분의 각 자릿수를 추출해 리스트(use)에 저장합니다.
- 가능한 모든 시간을 저장할 집합(possible)을 생성합니다.
- 백트래킹 함수 backtrack(path)를 정의합니다.
- path의 길이가 4가 되면, 앞 두 자리와 뒤 두 자리를 콜론(":")으로 연결하여 possible에 추가하고 종료합니다.
- use의 각 숫자 p에 대해 다음 조건을 검사합니다:
- path가 비어 있고(첫 자리 선택) p가 "2"보다 크면 안 됩니다. (시간의 십의 자리 제한)
- 첫 자리가 "2"일 때 p가 "3"보다 크면 안 됩니다. (23시 이상 불가)
- path의 길이가 2일 때(분의 십의 자리 선택) p가 "5"보다 크면 안 됩니다. (59분 이상 불가)
- 조건을 통과하면 backtrack(path + p)를 호출하여 다음 자릿수를 탐색합니다.
메인 로직 처리
- 빈 문자열로 backtrack()을 호출하여 모든 가능한 시간을 생성합니다.
- possible을 리스트로 변환한 뒤 오름차순으로 정렬합니다.
- 정렬된 리스트를 순회하며 현재 시간 s와 일치하는 항목을 찾으면, 그다음 항목(바로 다음 시간)을 반환합니다.
- s가 목록의 마지막 항목이라면(가능한 최대 시간), 첫 번째 항목으로 순환(wrap-around)하여 possible[0]을 반환합니다.
구현 예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, s):
use = [s[0], s[1], s[3], s[4]]
possible = set()
def backtrack(path):
nonlocal possible, use
if len(path) == 4:
possible.add(path[:2] + ":" + path[2:])
return
for p in use:
if (not (len(path) == 0 and p > "2")
and not (path == "2" and p > "3")
and not (len(path) == 2 and p > "5")):
backtrack(path + p)
backtrack("")
possible = list(possible)
possible.sort()
for i in range(len(possible) - 1):
if possible[i] == s:
return possible[i + 1]
return possible[0]
ob = Solution()
s = "03:15"
print(ob.solve(s))입력
"03:15"
출력
03:30
복잡도 분석
각 자릿수마다 최대 4개의 숫자를 시도하므로 백트래킹의 시간 복잡도는 O(4⁴)로 상수 수준이며, 추가로 정렬에 O(k log k)(k는 가능한 시간의 개수)가 소요됩니다. 따라서 전체적으로 매우 효율적인 해법입니다.