1차 코딩 테스트 마지막 문제입니다. 정답률과 난이도를 블로그에서 볼 수 있듯이, 1차 코딩 테스트에서 가장 어려운 문제입니다. 일단 구현부의 인풋을 계산하기 위한 전처리를 해야하고, 1초의 구간에 가장 많이 들어오는 구간의 개수를 효율적으로 따져야 하는 부분 등 많은 부분이 손이 갑니다. 여기서는 블로그의 부가설명이 있던 $O(nlogn)$ 의 풀이를 하지는 않고, 함정에 빠질 수 있는 부분들과 처리 부분을 하나 하나 살펴보겠습니다.
우선 주어진 인풋을 변환하는 부분부터 살펴보겠습니다. 2016-09-15 월의 시:분:초.밀리초 로 구분이 되어 있습니다. 인풋에서는 고정된 길이의 2016-09-15 시:분:초.밀리초 처리시간(ex : 2016-09-15 21:00:00.966 0.381s) 로 들어오기 때문에, 이전 문제를 풀었던 것과 마찬가지로 문자열에서 시간을 파싱하여 이를 정수로 저장하면 처리가 쉬워집니다. 소수점인 millisecond 부분엔 1000을 곱하여 정수로 저장할 수 있습니다. 이 때 주의해야 할 점이 하나 있습니다. 얼핏 생각하면 2016-09-15 라는 날짜는 매번 똑같기 때문에 필요가 없어보입니다. 하지만 중요한 것은 위의 시간은 종료가 된 시점이라는 것입니다. 아래와 같은 인풋이 예제입니다.
2016-09-15 00:00:00.000 0.5s
이렇게 인풋이 들어올 경우, 쿼리의 시작시간은 9월 14일 23:59 대로 넘어가게 된다는 점입니다. 그러므로 반드시 일수도 기록을 해야합니다. 이것이 첫번째 함정입니다. 9월 15일이기 때문에 int 형으로 저장할 수 없고, long long 문을 사용합니다. 사실 일자의 끝자리 5만 저장해도 되지만, 아래 첨부할 코드에서는 이해를 편하게 하기 위해 20160915 모두 저장하였습니다.
그 다음, 시간을 처리할 때 항상 주의해야 하는 점은 00초에서 1초를 빼면 99초가 아닌 59초가 된다는 점입니다. 따라서 시간을 뺄 때는 먼저 초에서 빼고, 음수가 되면 +60을 더하고 분에서 1을 뺍니다. 분이 음수가 되면 마찬가지로 시에서 1을 빼고, 분에 +60을 더합니다. 시가 음수가 된다면 상단에서 저장한 "20160915" 에서 1을 빼고, 24를 더합니다.
그 다음 쿼리가 정렬되어 있다는 보장이 없으므로 이를 시작시간 순서대로 정렬합니다. 이제 나머지는 개수를 포함하는 경우를 어떻게 효율적으로 따져주냐 입니다. 이는 블로그의 설명과 동일합니다. 특정 쿼리가 시작될 때(+1), 끝날 때(-1)를 제외한 사이 구간은 항상 동일한 결과값을 가지기 때문에 모두 따져줄 필요가 없습니다. 따라서 n개의 쿼리 중 i번째 쿼리에 대해 각각 $[S_i, S_i + 1000ms], [E_i, E_i + 1000ms]$ 구간을 기준으로 1초 내에 쿼리가 몇개 들어오는지 완전 탐색하면 2 * 2000 * 2000 번의 계산으로 알아낼 수 있습니다.
class Node
{
public:
long long begin, end;
bool operator <(const Node &n) const
{
return begin < n.begin;
}
};
int solve(vector<string> lines)
{
vector<Node> v;
for (string s : lines)
{
int hh, mm;
double ss, ts;
sscanf(s.c_str(), "2016-09-15 %d:%d:%lf %lfs", &hh, &mm, &ss, &ts);
long long day = 20160915, endtime = hh * 10000000 + mm * 100000 + ss * 1000;
endtime = stoll(to_string(day) + to_string(endtime));
ss -= ts;
if (ss < 0)
mm--, ss += 60;
if (mm < 0)
hh--, mm += 60;
if (hh < 0)
day--, hh += 24;
long long starttime = hh * 10000000 + mm * 100000 + ss * 1000;
starttime = stoll(to_string(day) + to_string(starttime));
v.push_back({ starttime, endtime});
}
sort(v.begin(), v.end());
int ans = 0;
for (int i = 0; i < v.size(); i++)
{
int cmp = 1;
for (int j = 0; j < v.size(); j++)
{
if (i == j) continue;
if (!(v[j].end < v[i].begin || v[i].begin+1000 < v[j].begin)) cmp++;
}
ans = max(ans, cmp);
cmp = 1;
for (int j = 0; j < v.size(); j++)
{
if (i == j) continue;
if (!(v[j].end < v[i].end || v[i].end + 1000 < v[j].begin)) cmp++;
}
ans = max(ans, cmp);
}
return ans;
}