[2018 Kakao Blind Recruitment] 추석 트래픽 Java 풀이
PROBLEM
https://programmers.co.kr/learn/courses/30/lessons/17676
SOLUTION
초당 최대 처리량을 구하는 방법을 찾아내야한다.
0초부터 마지막 끝시간까지 매 밀리초를 확인해야 하나 생각이 들었지만, 슬라이딩 윈도우 쓰면서 하더라도 밀리초단위로 움직이는 것은 무리로 보인다.
이 때, 모든 밀리초마다 확인이 필요하지 않다. 초당 최대 처리량이 변하는 순간은 요청 응답 완료시간 이전과 이후로 변화한다는 것을 알아채야한다.
문제 속 예시 사진을 보면서 빨간색 1초 범위를 상상속에서 움직여보자. 0초부터 조금씩 움직이면서 초당 최대 처리량이 증가할텐데 첫 번째 요청 응답이 완료된 시점을 지나면 초당 최대 처리량이 감소한다. 요청 응답 완료시간이 중요한 포인트임을 짐작해야한다.
요청 응답 완료시간을 중심으로 1초 범위를 검사를 한다. 1초 범위 내에 어떤 요청이 처리되는 중이라는 것은 아래 조건들을 만족하는 것이다. 이 조건들을 만족하면 처리 중이라고 판단하고 개수를 세어 초당 최대 처리량을 판단한다. (47~49번 라인)
- 요청의 시작 시간이 1초 범위 내에 있다.
- 요청의 끝 시간이 1초 범위 내에 있다.
- 1초의 시작점(또는 끝점)이 요청 처리 시간내에 있다.
따라서 동작 순서는 다음과 같다.
- 입력되는 문자열을 처리하여, 시작 시간, 끝 시간, 처리 시간을 가지는
Node를 만든다. - 각
Node별 끝 시간일 때, 1초 범위 동안의 처리량을 계산한다. - 그 중 최대값을 반환한다.
SOURCE CODE (JAVA)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.*;
public class Solution {
class Node {
int endTime, processTime, startTime;
Node(int endTime, int processTime) {
this.endTime = endTime;
this.processTime = processTime;
this.startTime = endTime - processTime + 1;
}
}
int N;
Node[] nodes;
public int solution(String[] lines) {
int answer = 0;
N = lines.length;
nodes = new Node[N];
for (int i=0; i<N; i++) {
String line = lines[i];
int et = getEndTime(line);
int pt = getProcessTime(line);
nodes[i] = new Node(et, pt);
}
for (int i=0; i<N; i++) {
int endTime = nodes[i].endTime;
int result = getProcessForOneMinute(endTime);
answer = Math.max(answer, result);
}
return answer;
}
private int getProcessForOneMinute(int start) {
int end = start + 1000 - 1;
int result = 0;
for (int i=0; i<N; i++) {
Node node = nodes[i];
if ((start <= node.startTime && node.startTime <= end) ||
(start <= node.endTime && node.endTime <= end) ||
(node.startTime <= start && start <= node.endTime)) {
result++;
}
}
return result;
}
private int getProcessTime(String line) {
String time = line.split(" ")[2];
time = time.substring(0, time.length()-1);
int result = (int)(Double.parseDouble(time) * 1000);
return result;
}
private int getEndTime(String line) {
String time = line.split(" ")[1];
String[] timeSplitted = time.split(":");
int hour = Integer.parseInt(timeSplitted[0]);
int minute = Integer.parseInt(timeSplitted[1]);
String[] secondSplitted = timeSplitted[2].split("\\.");
int second = Integer.parseInt(secondSplitted[0]);
int mill = Integer.parseInt(secondSplitted[1]);
int result = 0;
result += (hour * 1000 * 60 * 60);
result += (minute * 1000 * 60);
result += (second * 1000);
result += mill;
return result;
}
}
OFF THE RECORD
초반에 문자열 처리 부분에서 꼼꼼하게 처리하지 못한 부분이 있어서 헤맸었다. 또한 split() 함수에서 .을 사용하여 문자열을 나누려면 split("\\.")으로 작성해야 함을 배웠다.
요청 처리 완료를 기점으로 탐색을 해야한다는 사실을 파악했다면 어렵지 않지만, 그것을 파악하는 것이 어려운 것이었다.
댓글 남기기