Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 주어진 숫자를 조합해 만들 수 있는 최대 24시간 시간 구하기

문제 개요

4개의 숫자로 이루어진 배열이 주어졌을 때, 이 숫자들을 모두 사용하여 만들 수 있는 가장 큰 24시간제 시간을 찾아야 합니다. 24시간제에서 가장 작은 시간은 00:00이고, 가장 큰 시간은 23:59입니다. 자정(00:00)부터 기준으로 삼았을 때 더 많은 시간이 경과한 시간일수록 더 큰 시간으로 간주합니다. 결과는 "HH:MM" 형식의 길이 5짜리 문자열로 반환하며, 만들 수 있는 유효한 시간이 없다면 빈 문자열을 반환합니다.

예를 들어 입력이 [1,2,3,4]라면, 만들 수 있는 가장 큰 시간은 "23:41"입니다.

풀이 접근 방법

이 문제는 깊이 우선 탐색(DFS)과 백트래킹을 활용하여 4개의 숫자로 만들 수 있는 모든 순열을 생성한 뒤, 그중 유효한 시간 형식을 만족하는 값 중 가장 큰 것을 선택하는 방식으로 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.

1. 유효성 검사 함수 isValid()

  • 문자열 a를 매개변수로 받아 해당 문자열이 올바른 24시간제 시간인지 검사합니다.
  • a[0]이 '2'보다 크면 false를 반환합니다.
  • a[0]이 '2'이면서 a[1]이 '3'보다 크면 false를 반환합니다. (시간은 23시를 넘을 수 없음)
  • a[3]이 '5'보다 크면 false를 반환합니다. (분은 59분을 넘을 수 없음)
  • 위 조건을 모두 통과하면 true를 반환합니다.

2. 순열 생성 함수 dfs()

  • 배열 A, 결과 문자열 res, 현재 문자열 cur을 매개변수로 받습니다.
  • cur의 길이가 5가 되면, isValid(cur)가 참이고 cur이 res보다 클 때 res := cur로 갱신한 뒤 재귀를 종료합니다.
  • i를 0부터 3까지 반복하며 다음을 수행합니다.
    • A[i]가 -1이 아니라면(아직 사용하지 않은 숫자라면):
      • tmp := A[i]로 임시 저장
      • cur := cur + A[i] + '0'의 아스키 코드 (숫자를 문자로 변환하여 추가)
      • cur의 길이가 2가 되면 ':'을 이어 붙여 "HH:MM" 형태를 만듭니다.
      • A[i] := -1로 설정하여 사용 처리
      • dfs(A, res, cur) 재귀 호출
      • A[i] := tmp로 복원 (백트래킹)
      • cur의 마지막 문자를 삭제하고, 길이가 2가 되었다면 ':'도 함께 제거합니다.

3. 메인 메서드

  • res := 빈 문자열, tmp := 빈 문자열로 초기화합니다.
  • dfs(A, res, tmp)를 호출합니다.
  • res를 반환합니다.

참고로 4개의 숫자로 만들 수 있는 순열은 최대 4! = 24가지뿐이므로, 완전 탐색으로도 충분히 빠르게 해결됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   void dfs(vector<int>& A, string& res, string& cur) {
      if (cur.size() == 5) {
         if (isValid(cur) && cur > res)
            res = cur;
            return;
         }
         for (int i = 0; i < 4; ++i) {
            if (A[i] != -1) {
               int tmp = A[i];
               cur += A[i] + '0';
            if (cur.size() == 2)
               cur += ':';
               A[i] = -1;
               dfs(A, res, cur);
               A[i] = tmp;
               cur.pop_back();
               if (cur.size() == 2)
                  cur.pop_back();
            }
         }
   }
   bool isValid(const string a) {
      if (a[0] > '2')
         return false;
         if (a[0] == '2' && a[1] > '3')
            return false;
         if (a[3] > '5')
            return false;
         return true;
   }
   string largestTimeFromDigits(vector<int>& A) {
      string res = "", tmp = "";
      dfs(A, res, tmp);
      return res;
   }
};
main(){
Solution ob;
vector<int> v = {1,2,3,4};
cout << (ob.largestTimeFromDigits(v));
}

입력

{1,2,3,4}

출력

23:41