Byung Wook Park (박병욱)

Byung Wook Park (박병욱)

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

✔️ 문제

✔️ 문제 이해

  • 9월 15일 로그 데이터를 분석하여 초당 최대 처리량을 계산하는 문제다.
  • 초당 최대 처리량 : 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(1,000ms)간 처리하는 요청의 최대 개수를 의미
  • 입력 형식
    • solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
    • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
    • 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
    • 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 2016년 9월 15일 오전 3시 10분 33.010초부터 2016년 9월 15일 오전 3시 10분 33.020초까지 0.011초 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
    • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
    • lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

✔️ 알고리즘 설계

  1. 주어진 로그 정보 문자열을 적절히 파싱하여, 로그의 시작 시간과 끝 시간을 계산한뒤 vector 에 넣는다.

  2. vector를 탐색하며 로그의 시작시간으로부터의 1초구간, 로그의 끝시간으로부터의 1초구간에 대해 각각 로그가 포함된 개수를 계산하고 최대 값을 정답으로 저장한다.

✔️ 상세 구현설명

  • 로그의 시작점, 끝점 쌍을 저장하는 logTime이라는 구조체를 사용한다.
  • 로그 정보 문자열들을 sscanf를 사용해 파싱하고, 로그의 시작점과 끝점을 ms 단위로 변환한뒤 logTime 구조체 vector logList에 하나씩 넣는다.
  • logList를 탐색하며 로그의 시작점으로부터 1초, 끝점으로부터 1초 구간에 각각 로그가 몇 개 포함 되어있는지 확인한다.
  • 1초 구간에 로그가 포함되는지 확인하는 방법 : 로그의 시작점이 구간에 포함되거나, 로그의 끝점이 구간에 포함되거나, 로그가 1초 구간 전체에 걸쳐 포함되는지 확인하면 된다.
  • 03:10:33.010s ~ 03:10:33.020s동안 걸린 시간은 0.010s 같지만 0.011s이다. 문제 조건에서 처리시간은 시작시간과 끝시간을 포함한다고 했기 때문이다.
  • 예를들어, 5초부터 1초 구간은 5.000s ~ 5.999s 라고 할 수 있다. 끝 시간 5.999를 포함하기 때문이다. 이 말뜻은 5.999s ~ 6.000s 사이의 0.001s 를 포함 한다는 의미다. 따라서 1초 구간은 기준점ms ~ 기준점ms + 999ms 와 같이 나타낸다.

👨🏻‍💻 소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// 로그의 시작점(시간)과 끝점(시간)을 저장하는 구조체
typedef struct {
	int start, end; 
}logTime;

vector<logTime> logList;

int count(int start, int end) { 
	int ret = 0;

	for (logTime log : logList) {
		if ((start <= log.start && log.start <= end) // 로그 시작점이 1초 구간에 포함 되는지 검사.
			|| (start <= log.end && log.end <= end) // 로그 끝점이 1초 구간에 포함 되는지 검사.
			|| (start > log.start && end < log.end)) // 로그가 1초 구간 전체에 포함 되는지 검사.
			ret++;
	}

	return ret; // 1초구간에 포함된 로그 개수 반환.
}

int solution(vector<string> lines) {
	int answer = 0;

	for (int i = 0; i < lines.size(); i++) {
		int y, m, d, hh, mm;
		double ss, period;

		// sscanf를 사용하면 간단하게 문자열 파싱을 할 수 있다.
		sscanf(lines[i].c_str(), "%d-%d-%d %d:%d:%lf %lfs", &y, &m, &d, &hh, &mm, &ss, &period);

		// 시간을 ms 단위로 바꾼다.
		int end = (hh * 3600 * 1000) + (mm * 60 * 1000) + (int)(ss * 1000);
		int start = end - (int)(period * 1000) + 1; // 끝시간을 포함하기 때문에 +1 해준다. 

		// 로그의 시작점과 끝점을 vector에 넣어준다. 
		logList.push_back({ start, end });
	}

	for (int i = 0; i < logList.size(); i++) {
		// 로그의 시작점부터 1초 구간에 로그가 몇 개 포함되는지 검사.
		answer = max(answer, count(logList[i].start, logList[i].start + 999)); 
		// 로그의 끝점부터 1초구간에 로그가 몇 개 포함되는지 검사. 
		answer = max(answer, count(logList[i].end, logList[i].end + 999)); 
	}

	return answer;
}

✔️ 복기해야 할 지식

  • sscanf 를 사용해서 문자열을 쉽게 파싱할 수 있다. (티스토리에 정리하자)

✔️ 문제 회고

  • 문제에서 정의된 시작시간과 끝시간을 포함하는 처리시간을 잘 이해하지 못했다. 처리시간은 끝시간을 포함하는 것을 간과하고 1초 구간을 기준점ms ~ 기준점ms + 1000ms 로 계산했었다.
  • 첫 로그의 시작 시간 ~ 마지막 로그의 종료 시간까지 1ms 단위마다 1초 구간을 검사하도록 구현했더니 시간 초과가 났다. 00:00:00.000 ~ 24:00:00.000 와 같은 최악의 경우에서 총 86,400,000번 (24h = 86400000ms) 검사한다. 이는 너무 많은 시간이 걸린다. 로그의 시작점과 끝점에서만 포함되는 로그의 개수가 달라지기 때문에 시작점, 끝점에서만 검사하면 된다.
  • 처음에 문자열을 하나씩 탐색하면서 로그 시간을 파싱했는데 sscanf를 사용했더니 정말 간단하게 파싱할 수 있었다.