프로그래머스. 추석 트래픽

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

 

1초 동안 처리하는 요청의 최대갯수를 구하는 문제이다.

그런데 시간의 단위가 0.001초까지 내려가기 때문에 만약 모든 주어진 시간에 대하여 계산을 한다면 수행시간이 너무 커지게 된다.

따라서 요청이 시작되는 시간에서부터 1초, 요청이  끝나는 시간에서부터 1초인 구간에서 최대 처리 갯수를 구하면 된다.

 

또한 시간은 소수점까지 포함해서 주어진다.

처음에 나는 string을 double형으로 변경해서 계산했더니 c++의 부동소수점 오차 문제 때문에 틀렸다.

그 이후에 시간을 ms단위로 바꿔서 int형으로 계산해서 해결했다.

 

계산하는 시작 구간을 x, 끝나는 구간을 y라고 하고

어떤 요청의 시작 시간이 a, 끝나는 시간이 b라고 하면 

b < x or a > y 면 해당 요청이 계산구간에 포함되지 않는다.  

 

c++의 부동소수점 오차에 관한것을 잊고있었다...

이 문제를 풀면서 다시 찾아보게 되는 계기가 됐고 

이런 문제를 풀때 double, float 형을 int형으로 바꿀수 있다면 바꿔서 계산하도록 하자.

 

 

---

2022.02.14 

다시 푸는 과정에서 몇개의 테스트케이스가 틀렸는데 이유는 

1초 범위와 요청이 겹치는 경우는 

1. 요청시간이 1초 범위 내에 있을때 

2. 요청마감 시간이 1초 범위 내에 있을때 

3. 요청시간과 요청마감시간이 1초 범위를 감싸고 있을때 

인데 3번째 케이스를 누락해서 틀렸었다.