[프로그래머스] 추석 트래픽

문제 링크 : programmers.co.kr/learn/courses/30/lessons/17676

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

문제 유형

구현, Sweeping

 

문제 자체는 [백준]1689_겹치는 선분 과 비슷하다. 

위 문제처럼 각 구간의 시작점에 1, 끝점에 -1의 가중치를 둔 후 좌표의 오름차순으로 훑으며

가중치 합의 최댓값을 찾는 방식으로 접근할 수 있지만, 이 문제는 조금 다르게 접근해야 한다.

이 문제에서 요구하는 정답이 특정 시각을 기준으로 1초 길이의 구간 내에 들어오는 요청의 최대 개수를 묻기 때문이다.

 

즉, 겹치는 선분 문제에서는 다음과 같은 정답을 요구했다면,

이 문제는 다음과 같은 정답을 요구하기 때문이다.

따라서, 문제를 다음과 같이 바꿔준다면 겹치는 선분 문제와 동일한 해법으로 해결할 수 있다.

각 요청의 끝점을 999ms 늘린다.

 

[코드]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
 
vector<p> points;
 
int sweeping(){
    int ret = 0, cnt = 0;
    for(int i = 0; i < points.size(); i++){
        cnt += points[i].second;
        ret = max(ret, cnt);
    }
    
    return ret;
}
 
int get_len(string timestr){
    //x.xxx 형태로 들어옴
    int s = atoi(timestr.substr(0, 1).c_str());
    int ms = 0, div = 100;
    for(int i = 2; i < timestr.size(); i++){
        if(timestr[i] == 's') break;
        ms += (timestr[i] - '0') * div;
        div /= 10;
    }
    return s * 1000 + ms;
}
 
void process(string timestr, int len){
    int h = atoi(timestr.substr(0, 2).c_str());
    int m = atoi(timestr.substr(3, 2).c_str());
    int s = atoi(timestr.substr(6, 2).c_str());
    int ms = atoi(timestr.substr(9, 3).c_str());
    
    int basetime = (h * 3600 + m * 60 + s) * 1000 + ms;
 
    points.push_back({basetime + 999, -1});
    points.push_back({basetime - len + 1, 1});
}
 
bool compare(p a, p b){
    if(a.first == b.first) return a.second > b.second;  //끝점이 포함이므로
    return a.first < b.first;
}
 
int solution(vector<string> lines) {
    int answer = 0;
    
    for(int i = 0; i < lines.size(); i++)
        process(lines[i].substr(11, 12), get_len(lines[i].substr(24)));
    
    sort(points.begin(), points.end(), compare);
    answer = sweeping();
    
    return answer;
}

 

스위핑 자체의 시간복잡도는 O(N)이 된다.