Next Closest Time

Online Assessment 문제를 풀다가 좋은 문제를 발견했다. 난이도가 조금 있는 편이라서 헤맸는데 프로그래머스에서 카카오 문제를 풀 때랑 유사하게 접근해서 풀어봤다.

오랜만에 Backtracking 개념이 나왔고, 문제를 읽자마자 이건 시간 개념 + 모든 조합의 결과로 풀어야되겠다라는 생각이 들어서 접근했다. 그런데 답을 보니깐 너무 신기하고 신박한 해답이 많아서 좀 놀랐다.

class Solution {
public:
    string answer = ""; 
    int getMinute(string& time){
        int hh = stoi(time.substr(0,2)); 
        int mm = stoi(time.substr(3,2)); 
        
        return (hh * 60) + mm; 
    }
    
    void findClosest(vector<char>& digits, string& tmp, int startTime, int index, int& currTime){
        if(tmp.length() == 4){
            if(stoi(tmp.substr(0,2)) > 23 || stoi(tmp.substr(2)) > 59) return; 
            string someTmp = tmp.substr(0,2) + ":" + tmp.substr(2); 
            int tmpMinute = getMinute(someTmp); 
            
            if(tmpMinute > startTime){
                if(tmpMinute - startTime < currTime){
                    currTime = tmpMinute - startTime; 
                    answer = someTmp; 
                }
            } else if(tmpMinute < startTime){
                string day = "24:00"; 
                int dayMinute = getMinute(day); 
                if(tmpMinute + dayMinute < currTime){
                    currTime = tmpMinute + dayMinute; 
                    answer = someTmp; 
                }
            }
            
            
            return; 
        }
        
        for(int i = 0; i < digits.size(); i++){
            tmp += digits[i]; 
            findClosest(digits,tmp,startTime,i,currTime);  
            tmp.pop_back(); 
        }
    }
    
    string nextClosestTime(string time) {
        int startTime = getMinute(time); 
        vector<char> digits; 
        for(char& c : time){
            if(c != ':') digits.push_back(c); 
        }
        
        answer = time; 
        string tmp = ""; 

        int currTime = INT_MAX; 
        findClosest(digits,tmp,startTime,0,currTime); 
        
        
        return answer; 
    }
};