다시 풀어봄
일단 나는 이런 문제는 무조건 정수형으로 변환하여 푸는 것을 선호한다..
문제에서는 초단위의 경우 최대 소수점 셋째 자리까지로 설정을 해 주었기 때문에, Double 타입으로 변환후 x1000을 할 수 있다.
각 task의 시작시간 ~ 요청 완료 시간 까지를 milisec단위로 변환한 timeLines 배열을 생성한다.
- 이문제는, 응답 완료시간을 기준으로 오름차순을 주었다.
- 최대한 많은 요청들을 포함하려면 "어떤 요청의 응답완료시간부터" 1sec가 구간이 된다. 그래야, 그 시간에 끝나는 그 요청도 포함이 되기 때문이다.
- 이 구간에 포함되는 요청들은 "이 구간의 끝시간 " >= "요청의 시작시간" 인 요청들이다.
class Solution {
int[][] timeLines;
public int solution(String[] lines) {
int answer = 0;
int lLen = lines.length; // task의 개수
// timeLines : 시작시간 , 완료시간
timeLines = new int[lLen][2];
convertLines(lines);
// 구하기 : 모든 완료시간을 iterate하면서, 해당시간 + 1000 - 1 이, 어떤 작업의 시작시간 이상이면 count를 한다
int max = 0,cnt = 0;
int criteria = 0; // 기준이 되는 완료시간
for(int i =0 ; i<lLen;i++){
criteria = timeLines[i][1]+1000-1;
cnt = 1;
for(int j=i+1;j<lLen;j++){
if(timeLines[j][0]<=criteria)cnt++;
}
max = Math.max(max,cnt);
}
answer = max;
return answer;
}
public void convertLines(String[] lines){
String line = null;
int t = 0; // 요청완료시간 정보를 milisec 로 변환한 정보
for(int i =0;i<lines.length;i++){
line = lines[i];
String[] times = line.split(" "); // times[2] 는 처리하는데에 걸린 시간
String[] compT = times[1].split(":"); // 요청 완료 시간 관련 정보
// compT[0] 은 hh , compT[1]은 mm , compT[2]는 ss.sss
t = Integer.parseInt(compT[0])*3600;
t += Integer.parseInt(compT[1])*60;
t *= 1000;
t += (int)(Double.parseDouble(compT[2])*1000);
timeLines[i][1] = t; // 요청완료 시간 기록
timeLines[i][0] = t - ((int)(Double.parseDouble(times[2].split("s")[0])*1000) )+ 1; // 요청 시작 시간
// System.out.println(timeLines[i][0]+"~"+timeLines[i][1]);
}
}
}처음 풀 때
- 초당 최대 처리량은 응답 [완료 여부 상관x이] 임의 시간부터 1초간 처리하는 요청의 최대 개수를 의미한다.
- 고정길이 2016-09-15 hh:mm:ss.sss 처리시간T
- 처리시간 T는 최대 소수점 셋째 자리까지 기록 하며 뒤에는 초 단위를 의미하는 s로 끝난다.
- T는 0.001이상 3.000 이하이다.
- 입력 lines는 응답완료시간 S를 기준으로 오름차순 정렬되어있다.
- "완료"되지 않아도 된다는 것.
- 끝에서부터 Sliding Window를 해 봐도 될 것 인가?
- sliding window를 하더라도 0.001 s단위로 이동시켜야하는데, 시간복잡도가 괜찮을지 의문이다.
- Sliding Window같은 것을 사용시 이 문제는 범위가 매우 크기 때문에..오히려 이렇게 할 경우 시간 초과가 생길 위험이 크다.
[시간][분][초][밀리세컨드]
-
먼저 정규표현식을 잘 쓸 줄 알아야 겠다.
-
[ 띄어쓰기를 중심 ] 으로 split한다 "2016-09-15","hh:mm:ss.sss","Ts"
-
날짜 버리고
-
"hh:mm:ss.sss" 를 ":"중심으로 split한다.
-
Ts는 substring을 사용해 s를 없애고 이 String을 double로 변환한다. 이때 주의해야할 점이있다.
-
50분정도 고민한 결과 다른 사람 풀이를 보았다.
문제를 단순화 하는 것이 중요하다- 문제는 "끝 시간"을 "오름차순"으로 정보를 주었다.
- 내가 하던 생각
- ms 또한 보기 때문에, 어떤 log의 시간정보의 경계선이 아닌 곳으로부터 1초가 정답이 될수도 있다고 생각했다. 하지만 end기준으로 하면 큰 문제가 아니었다... !
먼저 시간단위를 조정한다.
-
"1초" 가 중요하고 , 나는 double형으로 할 경우 혼란이 생길 것 같지만 그게 더 편할 것 같긴 하다. s 단위로 저장한다.
-
나는 s로 변환 후 —> x1000을 해서 ms단위로 저장하겠다. 24X60x60x1000 =86400000 이기 때문에 int 타입으로 저장 가능하다.
-
시간이 hh:mm:ss.sss 이기 때문에,
-
hh x 3600 + mm x 60 + ss.sss 를 저장한다. (":" 를 기준으로 split한다)
-
ss.sss와 같은 String을 바로 Double로 변환 후 —> 1000을 곱하는 방식을 택했다
💥이 때, Double.parseDouble(String s) 사용시 지수 형식으로 나오게 되기 때문에, 그렇지 않게 하기 위하여 NumberFormat을 사용하였다.
-
-
각 로그에 대한 시작시간, 끝 시간에 대한 array를 각각 생성한다.
단순하게 생각하려 한다 .
-
전체탐색을 사용 한다. 전체 로그 개수가 2000개 정도 밖에 안 되기 때문에 전체탐색을 해도 괜찮은 문제였다. N^2이라하더라도 4백만개 정도이기 때문에 괜찮다.
-
문제에서 [ 끝 시간 ] 을 기준으로 [오름차순 ] 인 정보를 주었다는것과 + "완료된 것이 아니어도" 카운트 한다는게 중요하다
-
end array를 for문을 이용하여 돈다.
- 첫 번째 end를 기준으로 start array를 for문을 이용하여 돈다.
- end[i]시간을 기준으로 1초 가, i+1부터 n가지의 log들의 "start시간 이상"이어야 한다.
public static void set(int[] start, int[] end,String[] lines){
for(int i=0;i<lines.length;i++){
int endTime=0;
int startTime=0;
String[] seg = lines[i].split(" ");
// Drop seg[0] --> seg[1] : hh:mm:ss.sss --> seg[2] : ?s
String[] times = seg[1].split(":");
int hour = Integer.parseInt(times[0]);
int min = Integer.parseInt(times[1]);
int secmsec = (int)(Double.parseDouble(times[2]) *1000);
endTime += 3600 *hour;
endTime += 60*min;
endTime*=1000;
endTime += secmsec;
// seg[2]
int lapse = (int)(Double.parseDouble(seg[2].substring(0,seg[2].length()-1)) *1000);
startTime = endTime-lapse+1;
start[i]=startTime;
end[i] =endTime;
}
}
public static int solution(String[] lines) {
int answer = 0;
NumberFormat format = NumberFormat.getInstance();
format.setGroupingUsed(false);
int[] start = new int[lines.length];
int[] end = new int[lines.length];
set(start,end,lines);
int max = Integer.MIN_VALUE;
int curCnt=0;
for(int i=0;i<lines.length;i++){
curCnt=0;
int curCond = end[i]+1000-1;
for(int j=i;j<lines.length;j++){
if(curCond>=start[j]) curCnt++;
}
if(max<curCnt)max =curCnt;
}
answer = max;
return answer;
}
public static void main(String[] args) {
int res = 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"
});
System.out.println(res);
}20210923 다시 풀어봄
(28분)
- 초당 최대 처리량
- 요청의 [응답 완료 여부 관계 X ] , 임의 시간부터 1000sec안에 있는 task라면 처리량에 포함되는 것임
- 임의 시간부터 1000msec 간 처리하는 요청의 최대 개수
- 구해야 하는 것 : lines배열에 대해 [ 초당 최대 처리량 ] 을 리턴 한다.
- 주어지는 String[] lines는 2000개 이하의 로그 문자열
- 응답완료시간 S 처리시간 T 가 나타나 있다.
- 응답완료시간 S를 기준으로 오름차순 정렬되어있다.
- S의 형식 : 2016-09-15 hh:mm:ss.sss 형식
- T의 형식 : 소수점 셋째 자리까지 기록(가능) + 뒤에는 s로 끝남
- 0.1s
- 0.312s
- 2s
- 처리시간은 시작시간, 끝시간을 포함한다. → 0.010초 부터 시작해 0.011s 만큼 처리시간이라면 → 0.010 + 0.0.11- 0.001 인 것.
- 처리시간은 0.001 이상 3.000 이하이다.
- 응답완료시간 S 처리시간 T 가 나타나 있다.
풀이 생각
가장 먼저 드는 생각 : 단위의 변환
주어지는 로그 데이터의 형식이 2016-09-15 hh:mm:ss.sss 이기 때문에 s 단위 또는 msec 단위로 변환해야 할 것 같다. 나는 float형식에 익숙하지 않기에 정수형으로 변환하려 한다.
- msec단위인 경우 : 24 x 60 x 60 x 1000ㅍ = 8640만 → int 타입에 저장 가능하다
먼저 lines[i] 하나를 받아서 split해보자
String[] temp = lines[i].split(" ");
// temp[1]은 hh:mm:ss.sss 를 temp[2]는 T를 담고 있다.
String[] times = temp[1].split(":");
// - Integer.parseInt("01") —> 1으로 변환가능하다.
💥 문제를 느끼는 부분은 T가 주어지는 형식이 2s를 2.0s라고 주어지기도 하고 2.00s 로 주어지기도 한다는 것이다.
- 2.0s
- 2s
- 1.562s
- 이것을 그냥 Double 타입으로 전환하여 1000을 곱한 후 int타이으려 변환한다.
구간의 기준: 어떤 로그의 "완료시간"을 시작점으로
- 어차피 무조건 "어떤 로그의 완료시간"을 시작점으로 하는게 좋을 것 같다.
- 어떤 로그의 완료시간을 시작점으로 하는 1sec구간에 대하여, 다음 로그의 수행시간이 포함되는지를 체크하면 된다. --> 즉 완전탐색을 생각했다. - 완전 탐색 ?
- 2000개의 로그를 각각을 1sec의 시작점으로 하여, 그 로그 뒤의 로그들이 1sec 구간에 포함되는지 체크하기 → 2000 x 2000 이 되어도 400만 정도이기 때문에 가능할 것 같다.
- 또한, 이문제의 경우는 오름차순이니, 2000,1999,1998번...1번 이런 횟수로 수행되게 된다.
최종 코드
class Solution {
public int max = 0;
public void solve(int[] fin, int[] task){
int cnt =0;
// 전체 탐색
for(int i=0;i<fin.length;i++){
cnt =0;
// fin[i]+1000 - 1(i 번째 task의 완료시간을 포함하여 1sec 동안) 이 fin[j]-task[j]+1 (j번째 task의 수행시간동안 겹치는 시간이있는지를 )이상인지를 체크한다.
for(int j=i;j<fin.length;j++){
if(fin[i]+1000-1>=fin[j]-task[j]+1) cnt++;
}
if(max<cnt) max = cnt;
}
}
public int solution(String[] lines){
int answer =0;
int[] fin = new int[lines.length]; // 완료시간을 msec 단위로 저장
int[] task = new int[lines.length]; // 완료하는데 걸리는 시간을 msec단위로 저장
// 처리
String[] temp = null;
String[] times = null;
int cnt=0,i=0;
for(String line:lines){
cnt =0;
temp = line.split(" ");
times = temp[1].split(":");
cnt+=Integer.parseInt(times[0])*60*60; // 01
cnt+=Integer.parseInt(times[1])*60; // 00
cnt*=1000;
cnt += (int) (Double.parseDouble(times[2]) * 1000);
fin[i]=cnt;
task[i++] = (int) (Double.parseDouble(temp[2].split("s")[0]) * 1000);
}
solve(fin,task);
answer = max;
return answer;
}
}정확성 테스트
테스트 1 〉 통과 (0.76ms, 69.4MB)
테스트 2 〉 통과 (11.23ms, 86.3MB)
테스트 3 〉 통과 (11.93ms, 71.2MB)
테스트 4 〉 통과 (115.80ms, 92MB)
테스트 5 〉 통과 (2.46ms, 77.8MB)
테스트 6 〉 통과 (2.24ms, 69.4MB)
테스트 7 〉 통과 (18.98ms, 86.5MB)
테스트 8 〉 통과 (12.46ms, 75MB)
테스트 9 〉 통과 (2.71ms, 73.2MB)
테스트 10 〉 통과 (0.53ms, 75.9MB)
테스트 11 〉 통과 (0.57ms, 75.9MB)
테스트 12 〉 통과 (17.76ms, 82.6MB)
테스트 13 〉 통과 (2.32ms, 71.3MB)
테스트 14 〉 통과 (0.45ms, 75.5MB)
테스트 15 〉 통과 (0.45ms, 66.5MB)
테스트 16 〉 통과 (0.74ms, 70.4MB)
테스트 17 〉 통과 (2.70ms, 79.9MB)
테스트 18 〉 통과 (21.23ms, 80.6MB)
테스트 19 〉 통과 (23.43ms, 101MB)
테스트 20 〉 통과 (15.85ms, 94.4MB)
테스트 21 〉 통과 (0.39ms, 73.4MB)
테스트 22 〉 통과 (0.40ms, 72.9MB)- 확실히 전 보다 문자열 변환을 어떻게 할지에 대한 고민이 적어졌다.
- 풀이에 대한 고민은 조금 적어진 것 같다.
