🖇️ 문제 링크
코딩테스트 연습 - [1차] 추석 트래픽
이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량 은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.
https://programmers.co.kr/learn/courses/30/lessons/17676
📝 문제 분석
임의의 1초 구간에 동시에 처리한 로그의 최대값을 구하는 문제입니다.
일단 로그의 시간을 비교하기 쉽게 밀리세컨으로 바꿔줍니다. 그리고 위 그림의 형태처럼 나열하기 위해 시작 시간과 끝 시간으로 구분하여 따로 배열에 저장합니다.
종료 로그는 종료 후 1초까지 집계가 될 수 있기 때문에, 종료 시간 + 999밀리세컨을 더해줍니다.
시간 기준으로 오름차순 정렬을 하고, 시작 시간과 종료 시간이 1초 구간과 겹치면 둘 다 집계할 수 있기 때문에 시작 로그를 종료 로그보다 우선해서 정렬합니다.
이 후, 시간이 빠른 로그부터 순회하면서 시작 로그라면 cnt + 1, 종료 로그라면 cnt - 1을 해줍니다.
⌨️ 코드
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public int solution(String[] lines) {
ArrayList<Log> logs = new ArrayList<>();
// 시간을 밀리세컨드로 변환
for(String log : lines) {
String[] time = log.split(" ");
String[] arr = time[1].split(":");
int ms = Integer.parseInt(arr[0]) * 3600 * 1000
+ Integer.parseInt(arr[1]) * 60 * 1000
+ (int)(Double.parseDouble(arr[2]) * 1000);
int w = (int)(Double.parseDouble(time[2].substring(0, time[2].length() - 1)) * 1000);
// 시작 로그
logs.add(new Log(ms - w + 1, 0));
// 종료 로그, 이후 1초까지 영향을 미치므로 999밀리세컨을 더해준다
logs.add(new Log(ms + 999, 1));
}
int cnt = 0, answer = 0;
Collections.sort(logs, (o1, o2) -> {
if(o1.t == o2.t) return o1.se - o2.se; // 시간이 같다면 시작 로그 먼저
return o1.t - o2.t;
});
for(Log l : logs) {
if(l.se == 0) cnt++;
else if(l.se == 1) cnt--;
answer = Math.max(cnt, answer);
}
return answer;
}
public static class Log {
int t, se;
Log(int t, int se) {
this.t = t;
this.se = se;
}
}
}
Uploaded by Notion2Tistory v1.1.0