[프로그래머스] 추석 트래픽

 

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

 

2018년 카카오 블라인드 문제이며, Level 3 문제입니다. 위 문제에서 날짜는 고정값, 시간은 가변값이 핵심이다.

즉, 시간을 miliseconds 단위로 측정해서 구간별로 최대 처리량을 계산해야 한다.

유의할 점으로 위 문제를 해결하는 과정에서 모든 밀리 세컨드 단위로 for loop 로 돌 경우 시간 초과를 발생할 수 있다.

참고로, 시간 초과가 발생한 코드와 이를 해결한 코드를 비교해서 보면 더 좋을 것 같다.

 

(시간 초과)

• 아래 코드는 문자열 쪼갠 다음, 시간 + 밀리세컨드 분석을 하고, 시작과 끝을 배열로 만든 다음 0번째 시작점부터 마지막 끝점까지 for loop 를 돌게 되는데, 이런 경우 정확은 하지만 시간 초과가 발생하는 문제가 있다. (문제를 자세히 읽어보면 매초마다 최대 처리량을 계산할 필요가 없다는 것을 확인할 수 있다.)

import java.util.*;
class Solution {
    public static int getTime(String time) {
        String[] splitted = time.split(":");
        String[] seconds = splitted[2].split("\\.");
        int hour = Integer.parseInt(splitted[0]) * 3600;
        int minute = Integer.parseInt(splitted[1]) * 60;
        int second = Integer.parseInt(seconds[0]);
        return (hour + minute + second) * 1000 + Integer.parseInt(seconds[1]);
    }

    public static int getMiliseconds(String time) {
        double seconds = Double.parseDouble(time.split("s")[0]);
        seconds *= 1000;
        int miliSeconds = (int) seconds;
        return miliSeconds;
    }


    public static int solution(String[] lines) {
        int answer = 0;
        int[] starts = new int[lines.length];
        int[] ends = new int[lines.length];
        int maxCount = 0;

        for (int i = 0; i < lines.length; i++) {
            String[] splitted = lines[i].split(" ");
            int end = getTime(splitted[1]);
            int start = end - getMiliseconds(splitted[2]);
            starts[i] = start;
            ends[i] = end;
        }

        for (int i = starts[0]; i < ends[lines.length-1]; i++) {
            int count = 0;
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < lines.length; j++) {
                int diff = ends[j] - starts[j];
                if (ends[j] < i || i + 999 < starts[j] + 1) {
                    continue;
                } else {
                    count++;
                    list.add(j);
                }
            }
            maxCount = count > maxCount ? count : maxCount;
        }
        return maxCount;
    }
}

 

(시간 초과를 해결한 코드)

• for loop 를 돌 때, 각 로그의 종료점만 체크하면서 최대 처리량만 계산하면 적어도 시간초과에서는 문제가 발생하지 않을 것으로 예상해서 제출했는데, 정상적으로 모든 테스트케이스가 통과하였다.

import java.util.*;
class Solution {
    public static int getTime(String time) {
        String[] splitted = time.split(":");
        String[] seconds = splitted[2].split("\\.");
        int hour = Integer.parseInt(splitted[0]) * 3600;
        int minute = Integer.parseInt(splitted[1]) * 60;
        int second = Integer.parseInt(seconds[0]);
        return (hour + minute + second) * 1000 + Integer.parseInt(seconds[1]);
    }

    public static int getMiliseconds(String time) {
        double seconds = Double.parseDouble(time.split("s")[0]);
        seconds *= 1000;
        int miliSeconds = (int) seconds;
        return miliSeconds;
    }


    public static int solution(String[] lines) {
        int answer = 0;
        int[] starts = new int[lines.length];
        int[] ends = new int[lines.length];
        int maxCount = 0;

        for (int i = 0; i < lines.length; i++) {
            String[] splitted = lines[i].split(" ");
            int end = getTime(splitted[1]);
            int start = end - getMiliseconds(splitted[2]);
            starts[i] = start;
            ends[i] = end;
        }
        for (int i = 0; i < lines.length; i++) {
            int count = 0;
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < lines.length; j++) {
                int diff = ends[j] - starts[j];
                if (ends[j] < ends[i] || ends[i] + 999 < starts[j] + 1) {
                    continue;
                } else {
                    count++;
                    list.add(j);
                }
            }
            maxCount = count > maxCount ? count : maxCount;
        }
        return maxCount;
    }
}