[프로그래머스] 17676. 추석 트래픽
문제 링크
풀이 과정
7개의 테스트 케이스가 안맞았던 이유
DateTimeFormatter 와 LocalDateTime 클래스를 활용해 문제를 풀었습니다. 처음에는 LocalDateTime 대신에 LocalTime 클래스를 이용했는데, 문제에서 코드 실행 탭을 통해 보여지는 테스트 입력에 다음과 같은 입력이 있었습니다.
2016-09-15 00:00:00.000 3s
위의 입력 예의 처리 시작 날짜는 하루 전(2016-09-14 23:59:57.001) 으로 바뀌게 됩니다. 이는 시간만 가공하는 LocalTime 클래스로는 시간 비교를 할 때 예상과는 다른 결과를 내놨습니다. 아래 코드는 위 예제의 처리 시작 시간 23:59:57.001 과 응답 완료 시간 00:00:00.000 에 isBefore 메소드를 호출한 결과입니다.
LocalTime prev = LocalTime.parse("23:59:57.001", dtf);
LocalTime after = LocalTime.parse("00:00:00.000", dtf);
// 23:59:57.001 이 00:00:00.000 보다 이전이냐?
System.out.println("prev.isBefore(after) : " + prev.isBefore(after)); // false
위와 같이 날짜가 넘어가는 예외 상황들 때문에 LocalTime 이 아닌 LocalDateTime 클래스를 사용해야지만 모든 테스트 케이스를 맞을 수 있었습니다.
문제 조건인 처리 시간은 시작 시간과 끝 시간을 포함한다는 점을 유의해야 합니다. 위 그림과 같이 첫 번째 로그가 끝나는 시간부터 1초 구간은 첫 번째 로그와 두 번째 로그를 둘 다 처리할 수 있습니다.
for (int i = 0; i < lines.length; i++) {
int len = lines[i].length();
lines[i] = lines[i].substring(0, len - 1);
String[] tmp = lines[i].split(" ");
S[i] = tmp[0] + " " + tmp[1];
T[i] = tmp[2];
}
제일 먼저 문제에서 주어진 lines 문자열 배열을 통해 각 로그의 응답 완료 시간(S)와 처리 시간(T)를 분리합니다. 각 로그 맨 뒤에 붙은 문자 s를 제거하기 위해 substring 메소드를 이용했습니다. 또한 응답 완료 시간 배열 S에는 시간 뿐만 아니라 날짜도 포함시켰습니다. 이는 LocalTime 클래스가 아닌 LocalDateTime 클래스를 활용하기 위함입니다.
for (int i = 0; i < lines.length; i++) {
LocalDateTime start = LocalDateTime.parse(S[i], dtf).minusNanos((long) (Double.parseDouble(T[i]) * NANO)).plusNanos((long) (0.001 * NANO));
list.add(new Time(start, LocalDateTime.parse(S[i], dtf)));
}
Collections.sort(list);
다음으로 각 로그를 파싱해 구한 배열 S(응답 완료 시간)와 T(처리 시간)를 통해 각 로그의 처리 시작 시간 start 를 구합니다. LocalTime 객체에서 밀리초를 빼기 위해 minusNanos 메소드를 사용했습니다. LocalTime 클래스에는 밀리초에 관한 연산 메소드를 제공하지 않으므로, 나노 단위로의 변경이 필요했습니다. 처리 시간을 뺀 뒤에는, 시작 시간 또한 포함시키기 위해 0.001 초를 더해( plusNanos )줬습니다. 연산이 끝나면 리스트에 넣고 처리 시작 시간을 기준으로 오름차순으로 정렬합니다.
for (int i = 0; i < list.size(); i++) {
LocalDateTime start = list.get(i).start;
LocalDateTime end = list.get(i).end;
LocalDateTime startPlusOne = start.plusSeconds(1).minusNanos((long) (0.001 * NANO));
LocalDateTime endPlusOne = end.plusSeconds(1).minusNanos((long) (0.001 * NANO));
int cntStart = 0, cntEnd = 0;
for (int j = 0; j < list.size(); j++) {
LocalDateTime targetStart = list.get(j).start;
LocalDateTime targetEnd = list.get(j).end;
if ((targetStart.isBefore(startPlusOne) || targetStart.equals(startPlusOne)) && (targetEnd.isAfter(start) || targetEnd.equals(start)))
cntStart++;
if ((targetStart.isBefore(endPlusOne) || targetStart.equals(endPlusOne)) && (targetEnd.isAfter(end) || targetEnd.equals(end)))
cntEnd++;
answer = Math.max(answer, cntStart);
answer = Math.max(answer, cntEnd);
}
}
정렬이 끝났다면 각 로그를 기준으로 모든 가능한 경우의 수를 구합니다. 각 로그의 처리 시작 시간( start ) 과 응답 완료 시간( end ) 각각에 대해 1초를 더해, 해당 구간 안에 존재하는 모든 요청들을 셉니다.
if ((targetStart.isBefore(startPlusOne) || targetStart.equals(startPlusOne)) && (targetEnd.isAfter(start) || targetEnd.equals(start)))
cntStart++;
if ((targetStart.isBefore(endPlusOne) || targetStart.equals(endPlusOne)) && (targetEnd.isAfter(end) || targetEnd.equals(end)))
cntEnd++;
구간 내에 속해있는 지 판별은 start ~ startPlusOne, end ~ endPlusOne 의 두 구간을 기준으로 합니다. 아래와 같은 target 로그 막대들이 위에 적힌 두 구간 내에 들어오는지 양 끝점을 기준으로 판단합니다.
코드
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static int solution(String[] lines) {
final int NANO = 1000000000;
int answer = 0;
String[] S = new String[lines.length];
String[] T = new String[lines.length];
for (int i = 0; i < lines.length; i++) {
int len = lines[i].length();
lines[i] = lines[i].substring(0, len - 1);
String[] tmp = lines[i].split(" ");
S[i] = tmp[0] + " " + tmp[1];
T[i] = tmp[2];
}
ArrayList<Time> list = new ArrayList<>();
DateTimeFormatter dtf = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss.SSS");
for (int i = 0; i < lines.length; i++) {
LocalDateTime start = LocalDateTime.parse(S[i], dtf).minusNanos((long) (Double.parseDouble(T[i]) * NANO)).plusNanos((long) (0.001 * NANO));
list.add(new Time(start, LocalDateTime.parse(S[i], dtf)));
}
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
LocalDateTime start = list.get(i).start;
LocalDateTime end = list.get(i).end;
LocalDateTime startPlusOne = start.plusSeconds(1).minusNanos((long) (0.001 * NANO));
LocalDateTime endPlusOne = end.plusSeconds(1).minusNanos((long) (0.001 * NANO));
int cntStart = 0, cntEnd = 0;
for (int j = 0; j < list.size(); j++) {
LocalDateTime targetStart = list.get(j).start;
LocalDateTime targetEnd = list.get(j).end;
if ((targetStart.isBefore(startPlusOne) || targetStart.equals(startPlusOne)) && (targetEnd.isAfter(start) || targetEnd.equals(start)))
cntStart++;
if ((targetStart.isBefore(endPlusOne) || targetStart.equals(endPlusOne)) && (targetEnd.isAfter(end) || targetEnd.equals(end)))
cntEnd++;
answer = Math.max(answer, cntStart);
answer = Math.max(answer, cntEnd);
}
}
return answer;
}
public static class Time implements Comparable<Time> {
LocalDateTime start;
LocalDateTime end;
public Time(LocalDateTime start, LocalDateTime end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Time o) {
if (this.start.getHour() == o.start.getHour()) {
if (this.start.getMinute() == o.start.getMinute()) {
if (this.start.getSecond() == o.start.getSecond()) {
return this.start.getNano() - o.start.getNano();
}
return this.start.getSecond() - o.start.getSecond();
}
return this.start.getMinute() - o.start.getMinute();
}
return this.start.getHour() - o.start.getHour();
}
}
public static void main(String[] args) {
solution(new String[]{"2016-09-15 00:00:00.000 3s"});
// solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"});
// solution(new String[]{"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"});
// 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"});
}
}
댓글남기기