[2018 KAKAO BLIND RECRUITMENT] 추석 트래픽(C++)

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

코딩테스트 연습 - [1차] 추석 트래픽 | 프로그래머스

 

이 문제는 코드는 간단하지만, 아이디어를 떠올리는 것이 중요하다.

카카오 해설 코드에 부족한 부분을 채워서 설명하도록 하겠다.

 

---

 

 

문제에서 원하는 것은, 임의의 시간대에 1초동안 최대 몇 개의 처리량이 발생할 수 있는지 확인해야 한다.

모든 임의의 시간을 일일이 계산하기에는, 0.001초 단위이기 때문에 불가능하다.

 

 

전체 탐색이 아닌, 일부 탐색을 해야한다. 일부 탐색을 하는 시간대의 범위는 어떻게 선택해야 하는지가 문제의 핵심이다.

 

 

 

---

 

 

 

< 그림 >

 

위의 그림에서 임의의 시간대가 (1), (2), (3)이 있다. (1), (2), (3)을 자세히 살펴보자

(1), (2), (3) 각 각 내부에서 가장 발생시각이 늦은 트래픽을 살펴보자!

 

 

 

 

(1), (2), (3)의 기존의 시간 범위에서 가장 발생 시각이 늦은 트래픽의 시작 시간으로 시간 범위를 옮기면 어떻게 될까?

가장 발생시각이 늦기 때문에, 기존 범위에 있는 모든 트래픽들을 손실하지 않은 채 시간 범위를 변경할 수 있다.

 

 

 

 

이 경우에, (1), (2), (3)에서 가지고 있는 기존의 트래픽 처리량을 유지하면서, 추가적으로 걸쳐있는 트래픽들을 더 찾을 수 있다.

 

 

 

 

더 나아가서, 어떤 범위든지 가장 발생 시각이 늦은 트래픽이 존재한다. 가장 발생 시각이 늦은 트래픽을 상상해보자.

이 트래픽의 발생 시각에 가깝게 시간 범위를 조정하면, 기존 트래픽들의 처리 수를 유지한 채 새로운 트래픽들을 찾을 수 있다.

 

 

 

 

우리가 찾아야 할 특정 범위는 모든 트래픽의 시작 시간이 걸쳐지는 1초의 시간 범위이다.

 

 

 

 

---

 

 

위의 아이디어를 꼭 이해하고, 익숙해져야 한다. 카카오 해설에서는 트래픽의 양 끝을 모두 확인하므로 시간 복잡도가 2 * N^2이였지만, 이 아이디어를 이용하면 N^2에 문제를 해결할 수 있다.

 

 

 

이 아이디어를 바탕으로, 문제를 해결하면 된다. 

 

 

---

 

 

코드 구현 방법.

 

 

1. 시간 범위의 비교를 위해서, 함수 하나를 선언하고 string을 매개 변수로 받아 시간 값을 구해주도록 하였다.

 

2. 2중 포문으로, 트래픽 발생 1초전에서 발생까지 시간 범위를 기준으로 모든 트래픽을 비교하도록 구성했다. 

 

3. answer에 가장 큰 값을 갱신하도록 코드를 마무리한다. 

 

 

 

2번이 가장 핵심이 되는 코드 구현이지만, 아이디어만 생각할 수 있다면 나머지 코드 구현은 간단하다. 트래픽들의 시작 시간을 바탕으로 특정 조건을 만족했을 때 처리량에 포함이 될지만 구현해주면 된다.

 

 

---

 

코드 구현(C++).

 

#include <string>-
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
long long duration = 0;
 
long long timetoF(string time) {
    long long t = 0;
    ////hh(11 ~ 12)
    t += 36000000 * (time.at(11) - '0');
    t += 3600000 * (time.at(12) - '0');
 
    //// mm(14 ~ 15)
    t += 600000 * (time.at(14) - '0');
    t += 60000 * (time.at(15) - '0');
 
    //// ss(17 ~ 18)
    t += 10000 * (time.at(17) - '0');
    t += 1000 * (time.at(18) - '0');
 
    //// sss(20 ~ 22)
    t += 100 * (time.at(20) - '0');
    t += 10 * (time.at(21) - '0');
    t += 1 * (time.at(22) - '0');
 
    // duration(24, 26~28)
    long long temp = 1000;
    duration = 0;
    for (int idx = 24; idx < time.length() - 1; idx++) {
        if (time.at(idx) == '.')
            continue;
        duration += temp * (time.at(idx) - '0');
        temp /= 10;
    }
 
    return t;
}
 
int solution(vector<string> lines) {
    int answer = 0;
    for (int i = 0; i < lines.size(); i++) {
        int result = 0;
        long long e_t = timetoF(lines.at(i)) - duration + 1;
        long long s_t = e_t - 999;
        for (int j = 0; j < lines.size(); j++) {
            long long j_e_t = timetoF(lines.at(j));
            long long j_s_t = j_e_t - duration + 1;
            if (s_t >= j_s_t) {
                if (j_e_t < s_t);
                else
                    result += 1;
            }
            else {
                if (e_t < j_s_t);
                else
                    result += 1;
            }
        }
        answer = max(result, answer);
    }
 
    return answer;
}

 

예전에 풀어본 기억이 있어서, 다시 풀어봤지만 역시 쉽지 않은 문제이다.

노력하는 사람들에게 행운이 가길!