[프로그래머스] 2018 카카오 블라인드 #7 추석 트래픽 (Java)

#7 추석 트래픽

난이도 : LEVEL3

유형 : 구간합 

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

▸ 문제

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

▸ 입력

• solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

▸ 출력

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

 

문제 풀이  

해당 문제는 숫자도 너무 헷갈리고 탐색을 무작위하게 모든 것을 돌리기위해는 시간초과가 날 것 같아서 헤매다 결국 문제 해설을 참고하여 풀이하였다.

 

주요 아이디어

구간합을 구해야 하는 문제이다.

 

브루트포스로 첫 로그 부터 마지막 로그 시각까지 1ms 증가시키면서 1000ms 단위의 슬라이딩 윈도우로 풀면 24 * 3600 * 1000 * n * 1000ms가 걸리기 때문에 해당 방법은 안된다. n의 최대는 2000이기 때문에 약 172,800,000,000 (1천 7백억)연산이 필요하다.

 

그렇다고 각 로그의 시작부터 마지막 시각까지 1ms 씩 움직이면 time(ms)*n^2이 되며 time의 값은 대부분 천 단위(1s) 이상이기 때문에 마찬가지로 시간초과가 발생한다. 모든 time의 평균 1s라고 했을 때 약 4,000,000,000 (40억) 연산이 발생한다.

 

자세히 살펴보면 데이터가 변하는 순간은 각 로그의 시작점과 끝지점임을 발견해낼 수 있다. 따라서 각 로그 별 2번의 비교 연산만 수행하면 2*n^2으로 O(n^2)안에 연산을 처리할 수 있게 된다. 

 

시작점과 끝지점

 

설계

데이터 값의 최대 크기는 24*3600*1000 = 86,400,000으로 int형 범위안에 속한다.

1. 모든 로그 데이터들을 MiiliSec로 변환해주는 메소드를 만든다. timeToMilliSec(String line)
2. 각 로그의 시작점과 끝지점을 MilliSec를 구하여 저장한다. checkPoint.add(section[0]); checkPoint.add(section[1]);
3. 각 체크 포인트에 해당하는 로그들의 갯수를 카운트해준다. if(e < log[0] || log[1] < s ) continue;
4. 가장 큰 갯수(최대 처리량)을 출력한다. answer = Math.max(answer, cnt);

 

 

3번 로직은 구간 [s,e]에 해당하지 않는 데이터들만 따로 예외처리를 해줘서 카운트 해주는 것으로 아래 그림의 빨간 점선에 해당하는 로그들을 나타낸다.  if(e < log[0] || log[1] < s ) continue;

로그 예외처리

 

풀이 코드 

해당 문제를 O(nlogn)으로 풀 수 있는 방법이 있다고 하는데 아마 세그먼트 트리를 활용한 풀이일 것이다. 다음에 시간나면 세그먼트 트리 풀이도 해봐야겠다

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int solution(String[] lines) {
      int answer=0;
        List<Integer> checkPoint = new ArrayList<>();
        for(String line : lines) {
        	int[] section = timeToMilliSec(line);
        	checkPoint.add(section[0]);
        	checkPoint.add(section[1]);
        }
        Collections.sort(checkPoint);
        
        for(int standard : checkPoint){
        	int s = standard;
        	int e = standard + 999;
        	
        	int cnt=0;
        	for(String line : lines) {
        		int[] log = timeToMilliSec(line);
        		
        		if(e < log[0] || log[1] < s ) continue;
        		cnt++;
        	}
        	answer = Math.max(answer, cnt);
        }
        
        return answer;
	}
	
	static int[] timeToMilliSec(String line) {
        line = line.substring(11, line.length()-1);
		String[] data = line.split(" ");
		String[] time = data[0].split(":");
		double space = Double.parseDouble(data[1])*1000;
		
		int hhToMS = Integer.parseInt(time[0])*60*60*1000;
		int mmToMS = Integer.parseInt(time[1])*60*1000;
		double ssToMS = Double.parseDouble(time[2])*1000;
		
		int endTimeToMS = hhToMS + mmToMS + (int)ssToMS;
		int startTimeToMS = endTimeToMS - (int)space+1;
		
		return new int[] {startTimeToMS, endTimeToMS};
	}

}