[Programmers] [1차] 추석 트래픽

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/17676

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

시간 전처리만 잘하면 비교적 쉽게 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. lines 배열을 응답 완료 시간과 처리시간을 기준으로 전처리해준 뒤 orders 벡터에 {시작 시간, 완료 시간}을 넣어줍니다.

2. ms 단위로 슬라이딩 윈도우를 한다면 시간 초과가 발생할 것이 자명합니다.

2.1 따라서, 기준 로그의 완료시간 + 1초가 다른 로그의 시작 시간 이후라면 시간이 겹치는 것을 이용해 최대 처리량을 구해줍니다.

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <iostream>
	using namespace std;
	const int HOUR_TO_SECOND = 3600;
	const int MINUTE_TO_SECOND = 60;
	const int SECOND_TO_MS = 1000;
	const int SECOND = 1000;
	vector<pair<int, int>> orders;
	int solution(vector<string> lines) {
	for (string line : lines)
	{
	int hour = stoi(line.substr(11, 2)) * HOUR_TO_SECOND * SECOND_TO_MS;
	int minute = stoi(line.substr(14, 2)) * MINUTE_TO_SECOND * SECOND_TO_MS;
	int second = stoi(line.substr(17, 2)) * SECOND_TO_MS;
	int ms = stoi(line.substr(20, 3));
	int duration = (int)(stod(line.substr(24)) * SECOND_TO_MS) - 1;
	int time = hour + minute + second + ms;
	orders.push_back({ time - duration, time });
	}
	int result = 1;
	for (int i = 0; i < orders.size(); i++)
	{
	int endTime = orders[i].second + SECOND;
	int cnt = 1;
	for (int j = i + 1; j < orders.size(); j++)
	{
	int curStartTime = orders[j].first;
	if (curStartTime < endTime)
	{
	cnt++;
	}
	}
	result = max(result, cnt);
	}
	return result;
	}
	int main(void)
	{
	vector<string> lines = { "2016-09-15 20:59:57.421 0.351s"
	, "2016-09-15 20:59:58.233 1.181s"
	, "2016-09-15 20:59:58.299 0.8s"
	, "2016-09-15 20:59:58.688 1.041s"
	, "2016-09-15 20:59:59.591 1.412s"
	, "2016-09-15 21:00:00.464 1.466s"
	, "2016-09-15 21:00:00.741 1.581s"
	, "2016-09-15 21:00:00.748 2.31s"
	, "2016-09-15 21:00:00.966 0.381s"
	, "2016-09-15 21:00:02.066 2.62s" };
	cout << solution(lines) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~