Leetcode - 539. Minimum Time Difference

문제

시간이 HH:MM 형식의 string배열로 주어진다. 가장 차이가 작은 시간을 분단위로 리턴하라.

Input: timePoints = ["23:55", "23:59", "00:01"]
Output: 2

해결 O(nlogn)

먼저 HH:MM을 minute integer로 변환. 그리고 정렬. 그 뒤 인접 값을 비교해서 가장 작은것을 선택. 주의할것은 처음과 끝값(순환)도 체크해야함.

#include <string>

class Solution {
    int calc_minute(string time) {
        string h_str = time.substr(0, 2);
        string m_str = time.substr(3, 5);
        int h = stoi(h_str);
        int m = stoi(m_str);
        return h * 60 + m;
    }
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> minutes;
        int tsize = timePoints.size();
        int min_minute = INT_MAX;
        int max_minute = 24 * 60;
        
        for (auto it: timePoints) {
            // calculate hh:mm -> minute integer
            minutes.push_back(calc_minute(it));
        }
        std::sort(minutes.begin(), minutes.end());
        int diff = 0;
        int min_diff = 0;
        // 0 1 2 3
        // 0-1 1-2 2-3 3-0
        for (int i = 1; i < tsize; i++) {
            diff = minutes[i] - minutes[i - 1];
            if (diff < 24*30)
                min_diff = diff;
            else
                min_diff = max_minute - diff;
            min_minute = std::min(min_minute, min_diff);
        } 
        diff = minutes[tsize - 1] - minutes[0];
        min_diff = std::min(abs(max_minute - diff), abs(diff - max_minute));
        min_minute = std::min(min_minute, min_diff);
        return min_minute;
        
    }
};