[프로그래머스] 2018 KAKAO BLIND RECRUITMENT[1차] 추석 트래픽 - 자바(JAVA)

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

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

 

문제 해석

시스템 장애에 대비하기 위해 서버를 증설하고자 합니다.

증설 여부를 결정하기 위해 로그 데이터를 분석하여 초당 최대 처리량을 계산합니다.

초당 최대 처리량은 요청의 응답 완료 여부과 관계없이 임의 시간부터 1초간 처리하는 요청의 최대 개수를 의미합니다.

 

lines 배열은 최대 2000개의 로그 문자열로 되어 있습니다.

로그 문자열은 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있습니다.

lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있습니다.

 

예를들어 2016년 9월 15일 오전 3시 10분 33.020 0.011s는 다음과 같은 의미를 가집니다.

2016년 9월 15일 오전 3시 10분 33.010초부터 ~ 2016년 9월 15일 오전 3시 10분 33.020초까지 0.011초동안 처리된 요청을 의미합니다. 

 

 

다음과 같은 로그 타임라인을 가진다면 2번구간에서 7개를 1초에 처리할 수 있기 때문에 7이 출력됩니다.

 

문제 풀이 전 설계

2개의 포인터를 잡고 시작점과 끝점을 조절하며 특정구간에 가장 많은 처리할 수 있는 1초를 탐색해야 합니다.

만약 포인터를 움직이는 구간을 0.001으로 설정한다면 처리시간 3.000 * 2000개의 로그 문자열이므로 600만의 시간복잡도를 해결하면 됩니다.

 

여기서 주의할점은 로그가 처리되지 않는 구간이 있으면 그 구간을 뛰어넘어야 합니다.

 

예를들어 다음과 같은 구조의 로그 데이터가 들어올 수 있습니다.

로그1 시작~~~~ 로그1 끝

                                                                        로그2 시작 ~~~~ 로그2 끝

이렇게 될 경우 로그1시작~ 로그2끝으로 반복문을 돌리면 로그1 끝~ 로그2 시작 부분에는 시간이 낭비됩니다.

 

슬라이드 윈도우 방식으로 해결하지 않고 요청량이 변하는 순간은 각 로그의 시작과 끝뿐임을 이용하여 로그 별 2번의 비교 연산만 수행하면 되기 때문에 O(N^2) 만에 해결할 수 있습니다.

 

코드

public class Solution_카카오블라인드2018_추석트래픽 {
    public static void main(String[] args) {
        String[] lines = {
                "2016-09-15 20:59:57.421 0.351s",
                "2016-09-15 20:59:58.233 1.181s",
                "2016-09-15 20:59:58.299 0.8s",
                "2016-09-15 20:59:58.688 1.041s",
                "2016-09-15 20:59:59.591 1.412s",
                "2016-09-15 21:00:00.464 1.466s",
                "2016-09-15 21:00:00.741 1.581s",
                "2016-09-15 21:00:00.748 2.31s",
                "2016-09-15 21:00:00.966 0.381s",
                "2016-09-15 21:00:02.066 2.62s"
        };

        int answer= 0 ;
        int[] cnt = new int[lines.length];
        double complete;
        for(int i=0; i<lines.length; i++){
            //앞에 날짜는 시간을 계산하는데 의미가 없기 때문에 지우고, :과 s 또한 지워줍니다.
            lines[i] = lines[i].substring(11).replace(":","").replace("s","");

            int second = Integer.parseInt(lines[i].substring(0,2)) * 3600 + Integer.parseInt(lines[i].substring(2,4)) * 60 + Integer.parseInt(lines[i].substring(4,6));
            lines[i] = "" + second + lines[i].substring(6);

        }

        for(int i=0; i<lines.length; i++){
            String[] split = lines[i].split(" ");
            //완료 시간을 구해놓기
            complete = Double.parseDouble(split[0]);

            double area = complete+1;
            for(int j=i; j< lines.length; j++){
                split = lines[j].split(" ");
                //시작 시간 구하기
                double start = Double.parseDouble(split[0]) - Double.parseDouble(split[1]) + 0.001;
                if(start < area){
                    cnt[i]++;
                }
            }
        }

        for(int i=0; i<cnt.length; i++){
            answer = Math.max(answer,cnt[i]);
        }
        System.out.println(answer);
    }
}