[1차] 추석 트래픽(2018 카카오 블라인드 채용)

문제 링크

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

 

 

 

풀이

문제를 보고 든 생각은 구간별로 비교하면 되지 않을까? 하면서 선행처리 외에 반복문 두 개로 풀렸다.

 

요약을 하면, (전 처리 + 주 처리)로 나누어서 진행하였다. 빨리 풀어야되니까...

 

선행 처리  --- 미리 구간 처리를 위해 정리해놓음.

{

    반복문 ---- input 갯수만큼

    {

        stoi, stod로 정수형, 실수형으로 변환 후, total(초)를 구하였다. 대신 소수점을 없애기 위해 1000을 곱하였다.

        1) [타임라인의 시작 ~ 끝] ---- vector 컨테이너

        2) [1초 구간(끝 ~ 끝+1초 후)] ---- vector 컨테이너

        로 저장하였다.

    }

}

 

구간 처리 --- 답을 구하는 곳

{

    반복문 ---- 구간(끝 ~ 끝+1초후) 갯수만큼

    {

       반복문 ---- [시작 ~ 끝] 갯수 만큼

        {

            구간 안에 포함할 경우, count++;

            (= 타임라인의 끝이 구간의 시작보다 크고, 타임라인의 시작이 구간의 끝보다 작을 경우)

 

           Time out(임계값)이 3초로 그 뒤로는 break;를 걸었다.(낭비하지 않게)

            어차피 타임라인의 종료 시간으로 오름차순 되어 있으므로,

                타임라인의 시작이 구간의 끝과의 차이가 3이상부터는 break;

       }

      최대 count 갱신

    }

}

 

주의 !! ---- 부동 소수점 비교

 

1) cout으로 출력했더니 소수점이 잘려서 나왔다. --- N.001이 N으로 출력

2) printf(%.3lf)로 출력하면 제대로 값이 나왔다.

하지만 비교 단계에서 N.001 == N.001  -> false 나왔다????

3) double로 안되서 long double로 해도 안됨.

 

* VS code로 출력(100자리까지 printf로)

VS code 출력

- 빨간 줄, 두 값 비교시 false

- first1은 cout으로 출력

- first2는 printf로 출력

 

 

결론)

부동 소수점 비교는 조심하자!

부동 소수점 비교의 정밀도를 찾아보면 이해할 수 있다.

문제 푸는 것은 그냥 정해진 범위 내에 소수 자릿수들을 곱해서 정수로 만들자.(정수 연산이 더 빠르니까)

또는 double - double < 오차 범위 로 해도 될 듯 싶다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;
// hour: 11, 12
// minute: 14, 15
// second: 17, 18 + 20, 21, 22
// time: 24~ s전까지

int solution(vector<string> lines) {
    int answer = 0;
    vector<pair<int, int>> start_end;
    vector<pair<int, int>> section;
    
    // 선행 처리: 시작 시간(total 초), 끝 시간(total 초) 변환
    for(string s : lines){
        int hour = stoi(s.substr(11, 2));
        int minute = stoi(s.substr(14, 2));
        double second = stod(s.substr(17, 6));
        double time = stod(s.substr(24)) - 0.001;
        
        int endSec = (hour*3600 + minute*60 + second) * 1000;
        int startSec = endSec - time*1000;
        start_end.push_back(make_pair(startSec, endSec));   // 시작과 끝
        section.push_back(make_pair(endSec, endSec+999));    // 구간(끝도 포함하므로)
    }
    
    // 구간 처리
    int max = 0;
    for(int i=0; i<section.size(); i++){
        int count = 0;
        int start = section[i].first;
        int end = section[i].second;
        for(int j=0; j<start_end.size(); j++){
            if(start_end[j].second >= start &&
                 start_end[j].first <= end){
                // 구간 안에 포함
                count++;
            }
            else if(start_end[j].first-end > 2999)
                break;
        }
        if(max < count) max = count;
    }
    
    answer = max;
    return answer;
}