4자리 배열이 있다고 가정하고 만들 수 있는 가장 큰 24시간 시간을 찾아야 합니다. 가장 작은 24시간 시간은 00:00이고 가장 큰 시간은 23:59입니다. 00:00부터 시작하여 자정 이후 시간이 더 경과하면 시간이 더 커집니다. 답을 길이 5의 문자열로 반환해야 합니다. 반환할 유효한 시간이 없으면 빈 문자열을 반환합니다.
따라서 입력이 [1,2,3,4]와 같으면 출력은 "23:41"이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- isValid() 함수를 정의하면 문자열이 필요합니다.
- a[0]> '2'이면 -
- 거짓 반환
- a[0]이 '2'와 같고 a[1]> '3'이면 -
- 거짓 반환
- a[3]> '5'이면 -
- 거짓 반환
- 참을 반환
- dfs() 함수를 정의하면 배열 A, res, cur, 가 사용됩니다.
- cur의 크기가 5와 같으면 -
- isValid(cur) 및 cur> res인 경우 -
- res :=cur
- 반환
- isValid(cur) 및 cur> res인 경우 -
- 초기화 i의 경우:=0, i <4일 때 업데이트(i 1만큼 증가), 수행 -
- A[i]가 -1과 같지 않으면 -
- tmp :=A[i]
- cur :=cur + A[i] + '0'의 ASCII
- cur의 크기가 2와 같으면 -
- cur :=cur는 ':'와 연결
- A[i] :=-1
- dfs(A, res, cur)
- A[i] :=tmp
- cur에서 마지막 요소 삭제
- cur의 크기가 2와 같으면 -
- cur에서 마지막 요소 삭제
- A[i]가 -1과 같지 않으면 -
- 메인 방법에서 다음을 수행하십시오 -
- res :=빈 문자열, tmp :=빈 문자열
- dfs(A, res, tmp)
- 반환 결과
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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