카카오 추석트래픽

[1.문제 이해]

다음과 같이 요청시간의 시작지점과 끝지점이 주어졌을때 1초안에 처리가능한것 중 최대갯수를 찾으면 된다.

[2.접근]

• 시간별로 비교 및 연산 하기 쉽게 하기위해 변환한다. 예를들어 01:01:01 =>3661
• 검사할때 요청시간들의 시작지점 또는 끝점을 기준으로 탐색하면 효율적으로 접근 가능하다.

[3.알고리즘 선택]

우선순위큐: 데이터 요청시간을 하나의 막대라고 했을때
막대의 시작점을 기준으로 우선순위 큐에 집어넣는다. 그리고 큐에 있는 전송시작지점과 막대들의 간격차이를 기준으로 Count하며 탐색한다.

[4.코드]

#include <bits/stdc++.h>

using namespace std;

int solution(vector<string> lines) {
    int answer = 0;
    
    vector<int> times(lines.size());
    priority_queue<int> pq;
    
    // ms로 변환
    for(int i = 0; i < lines.size(); i++) {
        int hour = stod(lines[i].substr(11, 2));
        int minute = stod(lines[i].substr(14, 2));
        double second = stod(lines[i].substr(17, 6));
        int secTime = hour * 3600000 + minute * 60000 + second * 1000;
        times[i] = secTime;
    }
    
    // 끝 데이터부터 처음 데이터 방향으로 탐색
    int cnt = 0;
    int max = 0;
    for(int i = times.size() - 1; i >= 0; i--) {
        cnt++;

        // 전송 시점을 priority queue에 넣어준다. (priority queue를 쓴 이유는 빠른 탐색을 위해서)
        int temp = times[i] - (int)(stod(lines[i].substr(24, lines[i].size() - 25)) * 1000) + 1;
        pq.push(temp);
        
        // 거리가 1 넘어가는 건 다 꺼내기
        while(!pq.empty()) {
            if(times[i] + 1000 <= pq.top()) {
                pq.pop();
                cnt--;
            } else {
                break;
            }
        }
        if(cnt > max) max = cnt;
    }
    answer = max;
    return answer;
}