[프로그래머스(Programmers)][자바(java)] (Lv3) 추석 트래픽

 

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

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

 

문제 요약

• 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산하는 문제
  ( 초당 최대 처리량 :  요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수 )
• 입력 값은 String[] lines  ( 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있음 )
  -  응답완료시간 S  =>  "2016-09-15 %02d:%02d:%06.3f" 형식   (ex) 2016-09-15 01:00:04.001
  -  처리시간 T  =>  "%fs" 형식   (ex)  2.0s
   ( 처리시간은 시작시간과 끝시간을 포함 )  ( 0.001 ≦ T ≦ 3.000 )

 < 입출력 예제 3 >
▶ 입력 : [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]
▶ 출력 : 7
▶ 설명 : 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

 

 

문제 풀이

*  문자열 파싱

-  2016-09-15 인 로그만 있으므로 날짜는 고려하지 않아도 되고, 시간의 범위는 00:00:00.000 ~ 23:59:59.999 이다
-  lines[i]을 공백 문자(" ")를 기준으로 split하여 응답 완료 시간( S ), 처리 시간( T  )으로 parsing
-  응답 완료 시간을 콜론(":")을 기준으로 split하여 시간( h ), 분( m ), 초( s )로 parsing
-  시간이 초의 소수점 3번째 자리까지 표현되어 있으므로 단위를 ms로 변환
  ( 로그의 응답 완료 시간 = ( h*3600 + m*60 ) * 1000 + (int)( s * 1000 ) )
  ( 로그의 처리 시간 = (int)( t * 1000 ) )
-  로그가 시작하는 시점( ls = log[i][0] ) ~ 끝나는 시점( le = log[i][1] )을 각각 구하고 배열에 저장 ( 단위 : ms )
  ( 로그의 시작점 = 로그의응답 완료 시간 - 로그의처리 시간 + 1 )
  ( 로그의 끝점 = 로그의응답 완료 시간 ) 
-  임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 개수를 구할 때, 기준점이 될 수 있는 경우
   -  현재 로그의 시작점 ( log[i][0] )
   -  현재 로그의 끝점 ( log[i][1] )
-  기준 시작점( ps ) ~ 끝점( pe ) 사이에 해당하는 로그
  ( 기준 시작점 = 기준점 )
  ( 기준 끝점 = 기준 시작점 + 999 )
   -  로그의 시작점이 기준 시작점 ~ 끝점 사이에 있을 때
   -  로그의 끝점이 기준 시작점 ~ 끝점 사이에 있을 때
   -  로그의 시작점이 기준 시작점보다 작거나 같고, 로그의 끝점이 기준 끝점보다 크거나 같을 때
-  각 기준점 별 1초( 정확히는 999ms ) 간 처리하는 요청의 개수를 구하고 최댓값을 갱신하여 리턴

public class Solution {

	public int solution(String[] lines) {
		int n = lines.length, i, j, k;
		String l[], ll[];
		int he, me, mse, mss;  // hour/minutes_end, milli-second_end/start
		double se, t;		   // second_end
		int log[][] = new int[n][2];  // log_start/end
		for( i = 0; i < n; i++ ) {
			l = lines[i].split(" ");
			ll = l[1].split(":");
			t = Double.parseDouble( l[2].replace("s","" ) );
			he = Integer.parseInt( ll[0] );
			me = Integer.parseInt( ll[1] );
			se = Double.parseDouble( ll[2] );
			log[i][1] = mse = ( he*3600 + me*60 ) * 1000 + (int)( se * 1000 );
			log[i][0] = mss = mse - (int)( t * 1000 ) + 1;
		}
		int c, cm = 0, ps, pe, ls, le;  // cnt, cnt_max, point_start/end, log_start/end
		for( k = 0; k < 2; k++ ) {
			for( i = 0; i < n; i++ ) {
				ps = log[i][k];
				pe = ps + 999;
				c = 0;
				for( j = 0; j < n; j++ ) {
					ls = log[j][0];
					le = log[j][1];
					if( ( ps <= ls && ls <= pe ) || ( ps <= le && le <= pe ) || ( ls <= ps && pe <= le ) )
						c++;
				}
				cm = cm < c ? c : cm;
			}
		}
		return cm;
	}
}

import java.util.StringTokenizer;

public class Solution {

	public static int solution(String[] lines) {
		int n = lines.length, i, j, k, mse;  double t;  // milli-second_end
		int log[][] = new int[n][2];  // log_start/end
		StringTokenizer st, st2;
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( lines[i] );  st.nextToken();
			st2 = new StringTokenizer( st.nextToken(), ":" );
			t = Double.parseDouble( st.nextToken().replace("s","" ) );
			log[i][1] = mse = ( Integer.parseInt(st2.nextToken())*3600 + Integer.parseInt(st2.nextToken())*60 ) * 1000 + (int)( Double.parseDouble(st2.nextToken()) * 1000 );
			log[i][0] = mse - (int)( t * 1000 ) + 1;
		}
		int c, cm = 0, ps, pe, ls, le;  // cnt, cnt_max, point_start/end, log_start/end
		for( k = 0; k < 2; k++ ) {
			for( i = 0; i < n; i++ ) {
				ps = log[i][k];
				pe = ps + 999;
				c = 0;
				for( j = 0; j < n; j++ ) {
					ls = log[j][0];
					le = log[j][1];
					if( ( ps <= ls && ls <= pe ) || ( ps <= le && le <= pe ) || ( ls <= ps && pe <= le ) )
						c++;
				}
				cm = cm < c ? c : cm;
			}
		}
		return cm;
	}

	public static void main(String[] args) {
		
		System.out.println( solution( 
			new String[] {"2016-09-15 01:00:04.001 2.0s","2016-09-15 01:00:07.000 2s"} ) );
		System.out.println( solution( 
			new String[] {"2016-09-15 01:00:04.002 2.0s","2016-09-15 01:00:07.000 2s"} ) );
		System.out.println( solution( 
			new String[] {"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"} ) );
	}
}