[프로그래머스] [1차] 추석 트래픽
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17676
접근 방식
이전에 풀었던 단속 카메라에서 연장되는 선의 문제이다.
참고 : [프로그래머스] 단속카메라
최댓값은 각 로그의 끝지점에서의 1초안에 포함되는 로그의 갯수를 구하면 된다.
로그의 범위가 주어지지 않았기 때문에, 시작과 끝을 구해야 한다.
그리고, 모든 로그의 시작과 끝을 기준으로 1초의 범위를 지정해서, 해당 범위에 들어오는 로그의 갯수를 카운트하면 된다.
결과
소스 코드
import java.util.*;
class Solution {
public int solution(String[] lines) {
List<double[]> times = new ArrayList<>();
// 각 로그의 시작과 끝 시간 계산
for (String line : lines) {
String[] parts = line.split(" ");
double end = toSeconds(parts[1].split(":"));
double duration = Double.parseDouble(parts[2].substring(0, parts[2].length() - 1));
double start = end - duration + 0.001; // 종료시간에서 기간을 빼고, 0.001을 더하기
times.add(new double[]{start, end});
}
int answer = 0;
// 각 시간 구간에 대해 처리량을 계산
for (double[] currentTime : times) {
// 1초 구간을 기준으로 처리량을 계산 (1초 구간)
answer = Math.max(answer, count(times, currentTime[0]));
answer = Math.max(answer, count(times, currentTime[1]));
}
return answer;
}
double format(double d){
return d*10000 / 10000.0;
}
// 특정 시간 구간 내 로그 처리량 계산
private int count(List<double[]> times, double cur) {
int count = 0;
for (double[] time : times) {
double logStart = time[0];
double logEnd = time[1];
// 1초 구간 기준으로, 구간이 포함되는지 확인
if (logStart <= format(cur + 0.999) && logEnd >= cur) {
count++;
}
}
return count;
}
// 시간을 초 단위로 변환
private double toSeconds(String[] time) {
double hour = Double.parseDouble(time[0]) * 3600;
double minute = Double.parseDouble(time[1]) * 60;
double second = Double.parseDouble(time[2]);
return hour + minute + second;
}
}
-
시, 분, 초로 주어졌기에 계산하기 쉽도록 초로 변환 해 준다.
-
변환된 초를 기준으로, 시작과 끝을 구해서 범위 리스트를 만든다.
-
해당 범위 리스트를 기반으로, 시작과 끝에서 1초의 범위를 지정하여 해당 범위에 들어오는 로그의 최대 갯수를 구한다.
여기서 중요한 점은, 초를 카운트할 때, 밀리초로 구분하기 때문에 0.001을 빼고 반올림을 통해 자릿수를 맞춰줘야 한다는 점이다. (format 메소드의 존재의의)
만약, 그렇지 않다면 소수점 계산 방식으로 인해, 0.00000399994와 같은 숫자가 나오게 된다.
다른 접근 방식
나는 직접 주어진 시간을 초로 변환해서 사용했다. 하지만 Java에서는 Date라는 메소드를 통해 시간 처리가 가능하다.
SimpleDateFormat을 통해 날짜 형식을 지정해주고, Date를 통한 접근이 가능하다.
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
Date date = sdf.parse("2016-09-15 00:00:00.000");
date.getTime(); // 1473865200000
import java.util.*;
import java.text.*;
class Solution {
public int solution(String[] lines) throws ParseException {
List<Date[]> times = new ArrayList<>();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
// 각 로그의 시작과 끝 시간을 계산
for (String line : lines) {
String[] parts = line.split(" ");
Date end = sdf.parse(parts[0] + " " + parts[1]);
double duration = Double.parseDouble(parts[2].substring(0, parts[2].length() - 1));
long endTime = end.getTime(); // 끝 시간을 밀리초로 변환
long startTime = (long) (endTime - duration * 1000 + 1); // 시작 시간을 밀리초로 변환, 0.001초 더하기
times.add(new Date[] {new Date(startTime), new Date(endTime)});
}
int answer = 0;
// 각 시간 구간에 대해 처리량을 계산
for (Date[] currentTime : times) {
// 1초 구간을 기준으로 처리량을 계산 (1초 구간)
answer = Math.max(answer, count(times, currentTime[0]));
answer = Math.max(answer, count(times, currentTime[1]));
}
return answer;
}
// 특정 시간 구간 내 로그 처리량 계산
private int count(List<Date[]> times, Date cur) {
int count = 0;
long curTime = cur.getTime();
for (Date[] time : times) {
long logStart = time[0].getTime();
long logEnd = time[1].getTime();
// 1초 구간 기준으로, 구간이 포함되는지 확인
if (logStart <= curTime + 999 && logEnd >= curTime) {
count++;
}
}
return count;
}
}
- SimpleDateFormat을 통해 데이트 포맷을 지정한다.
- 밀리초를 기준으로 시작과 끝을 구해서 리스트에 저장한다.
- 리스트를 기준으로 시작과 끝(시작+999ms)에 포함되는지 카운트한다.
알게 된 점
소수점 형태로 계산할 일이 많이 없었는데, 계산 과정에서 정답이 계속 나오지 않아 무엇이 무엇인지 확인해보았더니 1초 처리 과정(+0.009, +0.001)에서 소수점 계산이 원하는대로 이루어지지 않았던 것이었다.
이는 부동소수점 오차 때문에 발생한 일이다.
원래는 수학적으로, 6.002 - 2.001 은 5.001이 되는 것이 맞다.
하지만, 컴퓨터는 이진수로 값을 저장하고 처리하기 때문에 실수를 표현하는 과정에서 작은 오차가 발생하게 된다. 따라서 두 값의 소수점이 정확하게 일치한다면 원하는 값을 얻을 수 있지만 ex) 6.002 - 2.002 = 4.0
6.002 - 2.001 과 같이 소수점의 값이 하나라도 다르다면 4.0009999999999994과 같이 4.001에 거의 근접한 값은 나오지만 전혀 다른 숫자가 탄생하게 된다.
그렇기 때문에, 소수점을 프로그래밍해야 하는 상황이 발생한다면, 꼭 주어진 데이터의 자릿수에 맞도록 추가 변환해 주는 것을 잊지 말아야 한다.
추가적으로, Java에서는 실수 계산의 정확한 보장을 위해 BigDecimal을 지원하고 있다. BigDecimal은 실수를 계산하는 과정에서 위와 같은 부동소수점 오차가 발생하지 않도록 해 주고 있다.