Java, LeetCode | 539. Minimum Time Difference

🚀 풀이 후기

시간을 활용한 문제라서 24:00 == 00:00 임을 생각해야 합니다.

🌒 문제 설명

시간을 분으로 바꿨을 때 최소 차이값을 반환하는 문제입니다.

Given a list of 24-hour clock time points in "HH:MM" format, 
return the minimum minutes difference between any two time-points in the list.
 

Example 1:

Input: timePoints = ["23:59","00:00"]
Output: 1


Example 2:

Input: timePoints = ["00:00","23:59","00:00"]
Output: 0
 

Constraints:

2 <= timePoints.length <= 2 * 104
timePoints[i] is in the format "HH:MM".

🌓 문제 풀이

class Solution {
    public int findMinDifference(List<String> timePoints) {
        // String 자료형의 시간을 int 형식으로 바꿉니다.
        List<Integer> minutes = timeToMinutes(timePoints);
        
        // 최소 차이값을 분으로 반환합니다.
        return minDifference(minutes);
    }

    public List<Integer> timeToMinutes(List<String> timePoints) {
        List<Integer> minutes = new ArrayList<>();
        for (String time : timePoints) {
            // : 을 기준으로 시와 분으로 쪼갭니다.
            int hour = Integer.parseInt(time.substring(0, 2)); // HH
            int minute = Integer.parseInt(time.substring(3)); // MM
            
            // Integer자료형의 List에 시간을 분으로 바꾼 값을 담습니다.
            minutes.add(hour * 60 + minute);
        }
        return minutes;
    }

    public int minDifference(List<Integer> minutes) {
        // 분을 오름차순으로 정렬합니다.
        Collections.sort(minutes);
        // 24:00 == 00:00 이므로 List에서 (맨 뒤에 저장된 값 - 맨 처음에 저장된 값)을 구합니다.
        int min = minutes.get(minutes.size() - 1) - minutes.get(0);
        
        // 24:00 == 1440분이므로 1440-min이 더 작은지 검사합니다.
        min = Math.min(min, 1440 - min);
        for (int i = 1; i < minutes.size(); i++) {
            // minutes List를 순환하며 가장 작은 분의 차이값을 구합니다.
            int diff = minutes.get(i) - minutes.get(i - 1);
            min = Math.min(min, diff);
        }
        return min;
    }
}

- 시간복잡도: O(N*log(N)+2N)

- 공간복잡도: O(N)

🌕 리팩토링

boolean[] times 배열에 timePoints의 시간을 ture/false로 저장합니다.

times 값이 true이면 index의 차이를 비교해서 최소값을 찾으면 됩니다.

정렬할 필요가 없으므로 시간복잡도가 줄어듭니다.

class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] times = new boolean[24 * 60];
        for (String timePoint : timePoints) {
            int hour = Integer.parseInt(timePoint.substring(0, 2));
            int minute = Integer.parseInt(timePoint.substring(3));
            int time = hour * 60 + minute;
            // System.out.println("time: "+time);
            if (times[time]) {
                return 0;
            }
            times[time] = true;
        }

        return minDifference(times);
    }

    public int minDifference(boolean[] times) {
        int left = Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < times.length; i++) {
            if (!times[i])
                continue;

            if (left == Integer.MAX_VALUE) {
                left = i;
                right = i;
            } else {
                min = Math.min(i - right, min);
                right = i;
            }
            // System.out.println("min: "+min);

        }
        return Math.min(min, 1440 - (right - left));

    }
}

N: 1440분

- 시간복잡도: O(N)

- 공간복잡도: O(N)

 

---

리트코드 문제

깃허브 코드