문제

Programmers Lv3, [1차] 추석 트래픽

핵심

• 9월 15일에 발생하는 초당 최대 처리량을 구해야 한다. 이는 임의의 시간부터 1초간 처리하는 요청의 최대 개수를 말한다.
• 문제를 풀기 위해 가장 중요한 부분은 입력 문자열 파싱과 초당 최대 처리량을 어떻게 구할지다.

1. 특정 시간 범위에 속하는지 알기 위해선 제일 작은 시간 단위(밀리초)로 변환해야 한다.
2. 초당 최대 처리량을 구하기 위해선 먼저 시작 시간과 종료 시간을 구해야 한다. 입력 예시를 보면 초당 최대 처리량을 구하기 위해 종료 시간 + 1000밀리초까지 같은 구간으로 보고 있다. DP로 구간 합을 구하는 것 같이 {시작 시간, 1}, {종료 시간, -1}로 파싱한 다음 시작 시간을 기준으로 정렬하면 겹치는 시간의 최대 개수를 파악할 수 있다.

int ans = 0;
int count = 0;
for (var log : logs) {
	count += log[1];
	ans = Math.max(ans, count);
}

• 참고로 java는 stable sort이므로 첫 번째 원소를 기준으로 오름차순 정렬하기만 하면 시작 시간과 종료 시간이 겹치는 로그 문자열에 대해 먼저 시작한 로그의 짝(-1)이 먼저 오는 게 보장된다.

int[] convertToMile(String time) {
	String[] split = time.split(" ");
	String[] times = split[1].split(":");
	
	int range = (int)(Double.parseDouble(split[2].substring(0, split[2].length() - 1)) * 1000);
	
	int hour = Integer.parseInt(times[0]);
	int minute = Integer.parseInt(times[1]);
	int secAndMile = (int)(Double.parseDouble(times[2]) * 1000.0);
	
	return new int[]{hour * 60 * 60 * 1000 + minute * 60 * 1000 + (int)secAndMile, range};
}

개선

• 문자열 파싱에 있어서 처음에 삽질을 많이 했다. 처리 시간이 주어질 때 소수점이 붙을 수도 있고, 없을 수도 있다. 처음엔 정수부와 소수부로 나눈(split) 다음 문자열에 "."이 포함되어 있다면 소수부 자릿수에 맞춰 곱하는 계산을 해주었는데, Double.parseDouble()을 이용하면 간편하게 가능하다.

range += Integer.parseInt(split2[0]) * 1000;
if (split[2].contains(".")) {
		int num = Integer.parseInt(split2[1]);
		if (split2[1].length() == 1) range += num * 100;
		else if (split2[1].length() == 2) range += num * 10;
		else range += num;
}

int range = (int)(Double.parseDouble(split[2].substring(0, split[2].length() - 1)) * 1000);

• 구간 최대 개수를 구할 때 초기에 생각했던 누적합 로직은 끝 시간에서부터 + 1000ms사이의 가장 큰 값을 찾는 것이다. 일단 밀리초 단위로 전체 시간을 순회해야 하며, 매번 끝 시간을 검사하여 끝시간 + 1000ms 사이의 최대값을 구해야한다. 로직도 복잡해질 뿐더러 느리다. 처리 기간 범위를 정하고, 시간 순으로 정렬하여 구간에 속하는 개수를 구하는 로직을 잘 떠올리자!
  

시간복잡도

• $O(n * logn)$

코드

import java.util.*;

class Solution {
                
    public int solution(String[] lines) {
               
        List<int[]> logs = new ArrayList<>();

        for (String line : lines) {
            int[] ret = convertToMile(line);
            int en = ret[0];
            int st = en - (ret[1] - 1);
            logs.add(new int[]{st, 1});
            logs.add(new int[]{en + 1000, -1});
        }

        logs.sort((a, b) -> Integer.compare(a[0], b[0]));

        int ans = 0;
        int count = 0;
        for (var log : logs) {
            count += log[1];
            ans = Math.max(ans, count);
        }

        return ans;
    }
    
    int[] convertToMile(String time) {
        String[] split = time.split(" ");
        String[] times = split[1].split(":");
        
        int range = (int)(Double.parseDouble(split[2].substring(0, split[2].length() - 1)) * 1000);
        
        int hour = Integer.parseInt(times[0]);
        int minute = Integer.parseInt(times[1]);
        int secAndMile = (int)(Double.parseDouble(times[2]) * 1000.0);
        
        return new int[]{hour * 60 * 60 * 1000 + minute * 60 * 1000 + (int)secAndMile, range};
    }
}