[프로그래머스-Level 03] - 추석 트래픽(c++)

문제 설명

추석 트래픽

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력 형식

• 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를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

입출력 예제

예제1

• 입력: [
  2016-09-15 01:00:04.001 2.0s,
  2016-09-15 01:00:07.000 2s
  ]

• 출력: 1

예제2

• 입력: [
  2016-09-15 01:00:04.002 2.0s,
  2016-09-15 01:00:07.000 2s
  ]

• 출력: 2

• 설명: 처리시간은 시작시간과 끝시간을 포함하므로
  첫 번째 로그는 01:00:02.003 ~ 01:00:04.002에서 2초 동안 처리되었으며,
  두 번째 로그는 01:00:05.001 ~ 01:00:07.000에서 2초 동안 처리된다.
  따라서, 첫 번째 로그가 끝나는 시점과 두 번째 로그가 시작하는 시점의 구간인 01:00:04.002 ~ 01:00:05.001 1초 동안 최대 2개가 된다.

예제3

• 입력: [
  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
  ]

• 출력: 7

• 설명: 아래 타임라인 그림에서 빨간색으로 표시된 1초 각 구간의 처리량을 구해보면 (1)은 4개, (2)는 7개, (3)는 2개임을 알 수 있다. 따라서 초당 최대 처리량은 7이 되며, 동일한 최대 처리량을 갖는 1초 구간은 여러 개 존재할 수 있으므로 이 문제에서는 구간이 아닌 개수만 출력한다.

  

   

---

내 풀이

 

이해하는데 무척이나 오래걸렸다 ㅠㅠ 

 

중요한 포인트는 

1. 시간부터 초까지를 1000ms 로 변환하여 하나의 수로 만들어야한다. 

2. '초당 처리량' 이라는 것은 각 로그 사이의 초를 말한다. 

 

2번은 사실 위의 그림만 보고도 알 수 있었지만 나는 이해하는데 좀 오래 걸렸다 .

 

 

1번을 위해서 만든 함수이다. 

int TimeToNum(string line) {
	string th = line.substr(11, 2);
	string tm = line.substr(14, 2);
	string ts = line.substr(17, 6);
	ts.erase(ts.begin() + 2, ts.begin() + 3); 

	int hour = stoi(th) * 60 * 60 * 1000;
	int minute = stoi(tm) * 60 * 1000;
	int sec = stoi(ts);

	return hour + minute + sec;
}

int ProcessToNum(string line) {
	string tmp = line.substr(24, line.size() - 25);
	double num = stod(tmp);
    	int res = num * 1000;

	return res; 
}

 - ProcessToNum() 함수는 처리시간을 integer로 바꾸는 함수이다 

ProcessToNum()

 

변환하는 함수를 만든 뒤에 알아둘 것은 아래와 같다.

 

• 시작시간 = 끝난 시간 - 처리시간 + 1
• 비교해나갈 끝난 시간 = 끝난 시간 + 1000(1초) 

위와 같은 변수를 선언해준 뒤 반복문으로 다음로그의 시작시간과 현재 로그의 끝난 시간을 비교하면서 answer++ 하면된다! 

 

처음에 끝난 시간과 시작 시간을 queue에 담아서 비교문에서 다음 시작시간이 현재 끝난 시간보다 크면 pop()을 하는 식으로 로직을 짰었는데 이게 뭔가 이상한 것 같다 테스트케이스는 다 통과하는데 채점하는 부분에서 2개인가 틀렸다. 도무지 답을 알 수 없었는데 이중 for문을 쓰니 해결됐다..... 하나도 빠짐없이 비교해야하나보다

 

전체 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

vector<string> lines;

int TimeToNum(string line) {
	string th = line.substr(11, 2);
	string tm = line.substr(14, 2);
	string ts = line.substr(17, 6);
	ts.erase(ts.begin() + 2, ts.begin() + 3); // 소수점 제거

	int hour = stoi(th) * 60 * 60 * 1000;
	int minute = stoi(tm) * 60 * 1000;
	int sec = stoi(ts);

	return hour + minute + sec;
}

int ProcessToNum(string line) {
	string tmp = line.substr(24, line.size() - 25);
	double num = stod(tmp);
	int res = num * 1000;

	return res; 
}

int solution() {
	int answer = 0;

	vector<int> process, end_point;

	for (int i = 0; i < lines.size(); i++) {
		string line = lines[i];
		int end_time = TimeToNum(line);
		int process_time =  ProcessToNum(line);

		//cout << i << "번 째 " << start_time << " " << end_time << "\n";
		process.push_back(process_time);
		end_point.push_back(end_time); 
	}

	int next_start_time, fur_time;
	for(int i=0; i<lines.size(); i++){
		int tmp = 0;
		fur_time = end_point[i] + 1000;
		for (int j = i + 1; j < lines.size(); j++) {
			next_start_time = end_point[j] - process[j] + 1;
			if (next_start_time < fur_time) {
				tmp++;
				continue;
			}
		}
		if (tmp > answer)
			answer = tmp;
	}
	return answer+1;
}

int main() {
	freopen("Text.txt", "r", stdin);

	int n, answer;

	cin >> n;
	cin.get();
	for (int i = 0; i < n; i++) {
		string input;
		getline(cin, input);
		lines.push_back(input);
	}

	for (int i = 0; i < lines.size(); i++)
		cout <<lines[i] << "\n";

	answer = solution();
	cout << answer;
}