추석 트래픽
문제: https://programmers.co.kr/learn/courses/30/lessons/17676
사진출처: 프로그래머스
input: ["2016-09-15 00:00:00.000 3s"]
위의 그림과 배열과 같이 [날짜 시간 프로세스처리시간]이 문자열에 담겨서 주어진다. 특정 시간대 1초에 가장 많이 프로세스가 중첩이 되는 갯수를 구하는 문제
이 문제를 풀다가 문제를 잘못읽고 해결하려해서 시간을 엄청 날려먹은 문제이다. 항상 문제를 대충 보고 풀다가 다시 문제를 읽는 안좋은 습관이 있다. 당장 고쳐야된다.
만약 실제 시험에 이런 상황이 발생한다면... 상상도 하기 싫다. 이번일을 교훈 삼아 정말로 앞으로는 문제를 다 파악하고 시작하자.
해결방법은 모든 경우의 수를 다 구해줬다. 카카오 문제여서 효율성 검사가 있으면 어떡하나하고 일단 이방법으로 구현하고 효율성에서 걸리면 다른 방법을 생각하자라고 생각하고 풀었는데 다행히도 효율성은 없었다.
해결방법
위에서도 말했듯이 모든 경우를 다 구해줬다. 모든 경우의 기준은 각로그의 마지막순간~1초 사이에 몇개의 프로세스가 진행중인지 배열에 넣어서 배열의 최댓값을 반환해줬다.
- lines를 순회하며
parseTime():시간(time)과 처리시간(process)을 이용해 로그의 시작시간(s)과 끝시간(markEndTime)을 구해준다. - 현재 로그 뒤에 있는 로그들과 비교해줘야 되기 때문에
const restArr = arr.slice(idx + 1);로 뒤의 로그들을 배열로 만들어준다. restArr을 순회하며 각 로그가 markEndTime~markEndTime+1(초) 사이에 있는지 판단해준다. 총 3가지의 경우가 있다. 현재 로그의 시작,끝을 start,end라고 하겠다.- start<=markEndTime<=end (markEndTime이 로그 사이에 있는경우)
- start<markEndTime+1<end (markEndTime+1이 로그 사이에 있는경우)
- 로그가 markEndTime,markEndTime+1 사이에 있는경우
처리시간은 시작시간과 끝시간을 포함한다. 라는 문제에 집중해서 비교해줘야한다.
- 위에서 true로 판단 되면 count++ 해주고 모든 로그를 다 순회하면 answer배열에 넣어준다.
- 배열 중 최댓값을 출력한다.
parseTime(time,process)
시간(time)과 처리시간(process)을 입력받아서 시작,끝 시간을 초로 바꿔주는 역할을 한다.
특별한 것은 없고 시작시간을 포함하기 때문에 process-=0.001을 해준 뒤에 시작시간을 구했다.
시작시간 = 끝시간 - process
code
function solution(lines) {
var answer = [];
lines.forEach((line, idx, arr) => {
const [date, time, process] = line.split(' ');
const restArr = arr.slice(idx + 1);
let [s, markEndTime] = parseTime(time, process);
let count = 1;
restArr.forEach((v) => {
const [date, time, process] = v.split(' ');
const [start, end] = parseTime(time, process);
if (
(markEndTime >= start && markEndTime <= end) ||
(markEndTime + 1 > start && markEndTime + 1 < end) ||
(start >= markEndTime && end < markEndTime + 1)
)
count++;
});
answer.push(count);
});
return Math.max(...answer);
}
function parseTime(time, process) {
let [h, m, s] = time.split(':');
const end = h * 3600 + m * 60 + s * 1;
const processTime = process.slice(0, process.length - 1) * 1 - 0.001;
const start = end - processTime;
return [start, end];
}마무리
문제만 집중해서 읽었더라면 오래걸릴문제는 아니었던것 같다.
근데 모든 경우를 다체크하는 경우 시간복잡도가 O(N^2)로 높은 편이다. 실제 상황에서는 엄청나게 많은 로그가 들어올 텐데 그 때는 어떻게 처리를 해줘야 될까...라는 생각이 든다.
첫 시도에는 시간기준으로 각 로그당 시작부터 끝까지 0.001초씩 더해주면서 객체에 key,value값으로 저장했다. 근데 나는 0.001초만 더해줬는데 1.001+0.001 = 1.0019999999999998 이런식으로 나왔다. 왜 그런지 알아봤더니만
대부분의 프로그래밍언어 (js포함)은 IEEE 754 standard 에 따라 소수도 2의 제곱으로 나타난다는데 그래서 1/10은 사실상 0.1이 아닌 0.1000000000000000055511151231257827021181583404541015625 이것..이라는 사실을 알게됐다.
출처: https://stackoverflow.com/questions/588004/is-floating-point-math-broken
대략적인 설명이지 자세한 설명은 위의 스택오버플로우 링크에 들어가면 나온다. 알쓸신잡 같은 내용이다.
그래서 소수점을 반올림하려면 toFixed()를 사용해야 된다는 것을 알게 됐다.
본론으로 돌아가 위의 방법은 실패로 거듭났다. 그리고 좋지 못한 방법인 것도 당연하다. 메모리가 어마무시하게 잡아 먹힐 것같다.
결론적으로는 실제 카카오에서는 저런 경우 어떤 방법으로 파악할지가 궁금하다!
