Baekjoon 21774 가희와 로그 파일 JAVA

21774번: 가희와 로그 파일

문제

로그 파일이 하나 있습니다. 이 로그 파일에는 N개의 로그가 저장되어 있습니다.

가희에게 Q개의 임무가 주어졌습니다. 가희는 각 임무마다 시작 시각, 종료 시각, 로그 레벨을 제공받습니다.

가희는 매 임무마다 주어진 시작 시각과 종료 시각 사이에, 로그 레벨이 lv 이상인 로그가 몇 번 발생하였는지 답해야 합니다.

이 때, 시작 시각과 종료 시각에 발생한 로그도 답을 계산하는 데 포함해야 합니다.

가희를 도와 임무를 수행하는 프로그램을 작성해 주세요.

입력

1번째 줄에 로그 파일에 있는 로그의 갯수 N과 쿼리의 갯수 Q가 주어집니다.

2번째 줄부터 N+1번째 줄까지, 로그 발생 시각과 LV이 #으로 구분되어 주어집니다.

N+2번째 줄부터 N+Q+1번째 줄까지 Q개의 임무가 다음 형식으로 주어집니다.

시작 시각#종료 시각#LV

시작시각, 종료 시각, 로그 발생 시각은 YYYY-MM-DD hh:mm:ss형식으로 주어집니다.

출력

임무에 대한 답을 한 줄에 하나씩 출력해 주세요.

풀이

누적합을 이용하여 해결하는 문제이다.

입력되는 로그의 값은 시간순서대로 입력이 되기에 입력을 받으면서 StringTokenizer를 이용하여 Lv만 분리하여 준다.

또한 문제에 존재하는 조건의 경우 동일한 시간에 여러개의 로그가 발생할 수 있다.

가장 앞의 시간을 찾을때 범위를 벗어나기 않기 위해서 입력될 수 없는 값인 1999-12-31 23:59:59 로그를 추가해준다.

이후에 입력받으면서 lv에 대한 정보를 lvs배열 [i]번째 행의 [0]열에 저장해준다.

lvs배열의 경우 lvs[입력되는 순서][0] 입력되는 값, lvs[입력되는 순서][lv의 누적합]으로 구성

모든 로그에 대한 입력이 끝난 이후에는 입력되지 않는 값인 2222-12-31 23:59:59를 입력함으로 이전과 마찬가지로

검색에 대한 범위를 안전하게 만들어준다.

 

이후 0열에 저장된 값을 이용하여 lv 이상인 로그가 발생한 모든 경우를 lvs에 만들고 누적합 배열로 구현하여 준다.

 

입력되는 탐색로그에 따라서 시작 시각부터 종료 시각까지 이분탐색을 이용하여 탐색해간다.

문제에서의 조건으로 동일한 시간에 여러개의 로그가 있을 수도 있기에 중복을 허용하는 l의 값과 r의 값이 같거나 작다면 계속하여 탐색하는 방법으로 동일한 시간의 가장 처음 등장하는 값까지 탐색한다.

탐색이 끝난 후 누적합 배열을 이용하여 사이에 존재하는 값들에 대한 결과를 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n=Integer.parseInt(st.nextToken()), q=Integer.parseInt(st.nextToken());
		int [][] lvs = new int [n+1][7];	// 누적합을 이용하여 사이합을 찾기 위한 lvs 배열
		String [] log = new String[n+3];
		log[0]="1999-12-31 23:59:59";	// 입력으로 주어지지 않는 가장 오래된 로그
		for(int i=1;i<=n;i++) {	// 로그 입력
			st = new StringTokenizer(br.readLine(),"#");	// #을 구분으로 입력 로그를 분리
			log[i]=st.nextToken();
			lvs[i][0]=Integer.parseInt(st.nextToken());
		}
		log[n+1]="2222-12-31 23:59:59";	// 입력으로 주어지지 않는 가장 최근 로그
		
		for(int i=1;i<=n;i++)	// 최대합은 0행에 저장후, lv6의 경우 lv1~lv6범위를 만족하기에 그만큼 범위합을 채워줌
			for(int j=1;j<=lvs[i][0];j++)
				lvs[i][j]++;
		
		for(int i=1;i<=n;i++)	// 누적합 배열 생성
			for(int j=1;j<=6;j++)
				lvs[i][j]+=lvs[i-1][j];
		
		String s, e;	// 이분탐색으로 범위사이의 값을 찾는 로그시간
		for(int i=0;i<q;i++) {
			int l=0,r=n+1,m, start, end;
			st = new StringTokenizer(br.readLine(),"#");
			s=st.nextToken();
			e=st.nextToken();
			int lv=Integer.parseInt(st.nextToken());
			
			while(l<=r) {	// 중복을 허용하는 최소값을 찾는 이분 탐색
				m=(l+r)/2;
				if(log[m].compareTo(s)<0)
					l=m+1;
				else
					r=m-1;
			}
			start=l;
			
			l=0;
			r=n+1;
			while(l<=r) {	// 중복을 허용하는 최대값을 찾는 이분 탐색
				m=(l+r)/2;
				if(log[m].compareTo(e)<=0)
					l=m+1;
				else
					r=m-1;
			}
			end=r;
			
			sb.append(lvs[end][lv]-lvs[start-1][lv]+"\n");	// 누적합을 이용하여 최대시간에서 최소시간의 값을 빼서 사이값을 찾음
		}
		System.out.println(sb.toString());
	}
}