[Programmers 코딩 연습] [1차] 추석 트래픽 [Level 3]
알고리즘 기법
- Greedy
설명
문제를 푸는 전략은 다음과 같다.
처리시간의 시작과 끝을 start_time, end_time이라고 하자.
(end_time = start_time + 1s - 0.001s)
어떤 일의 처리구간을 '막대'라하자. (아래 그림 참조)
(1)의 경우를 보자.
(1)처럼 처리시간을 잡고 몇개의 일을 처리했는지 세는 것은 비효율적이다.
왜냐하면 처리시간의 시작점인 start_time과 첫 번째 막대의 끝점을 맞춰야 더 많은 막대를 처리할 수 있기 때문이다. (아래 그림 참조)
따라서 첫 번째 막대부터 시작해서 마지막 막대까지 각각 막대의 끝점과 start_time을 맞추었을 때 (start_time~end_time)안에 얼마나 많은 막대를 처리 하는지 구하여 그 값들 중 가장 큰 값을 고른다면 답을 구할 수 있다.
다음으로 생각해야할 것은 "hh:mm:ss.sss" 문자열을 어떻게 비교하는지에 대해서다.
가장 간단한 방법은 시간, 분, 초, 밀리초를 전부 밀리초 단위로 바꿔서 비교를 하는 것이다.
integer의 범위를 넘어가지 않을까 걱정할 수도 있지만, 24x60x60x1000은 1억이 채 되지 않으니 걱정하지 않아도 된다.
ex) "23:59:18.456" -> ((((23 x 60) + 59) x 60) + 18) x 1000 + 456 -> 86,358,456
소스코드
#include <string>
#include <vector>
using namespace std;
int solution(vector<string> lines) {
int answer = 0;
int cnt;
int hour, min, sec, msec;
int sec_temp, msec_temp;
int time1, time2;
const int doing_time = 1000;
int doing_start, doing_end;
int i, j, len;
vector<vector<int>> lines_int;
// 문자열을 밀리초 단위의 시간으로 변경해서 저장.
for (string &line : lines) {
sscanf(line.c_str(), "2016-09-15 %d:%d:%d.%d %d.%ds", &hour, &min, &sec, &msec, &sec_temp, &msec_temp);
time1 = 60 * hour + min;
time1 = 60 * time1 + sec;
time1 = 1000 * time1 + msec;
time2 = 1000 * sec_temp + msec_temp;
lines_int.push_back({time1, time2});
}
//최대 개수 구하기 (doing start, doing_end는 처리시간 T의 시작, 종료 시각)
for (i = 0, len = lines_int.size(); i < len; i++) {
doing_start = lines_int[i][0];
doing_end = doing_start + doing_time - 1;
cnt = 1;
for (j = i + 1; j < len; j++) {
// lines_int[j][0] - lines_int[j][1] 일의 시작 시각
// lines_int[j]가 처리시간 T (doing_start ~ doing_end) 안에 포함된다면 cnt++
if (!(lines_int[j][0] - lines_int[j][1] + 1 > doing_end || lines_int[j][0] < doing_start))
cnt++;
}
if (answer < cnt)
answer = cnt;
}
return answer;
}
참고
scanf는 standard input, 즉 콘솔로부터 값을 입력 받는 함수고, fscanf는 파일, sscanf는 문자열로부터 값을 입력 받는다.
따라서 "2016-09-15 23:45:18.456"을 정수로 뽑아내려면,
sscanf("2016-09-15 23:45:18.456", "%d:%d:%d.%d", &hour, &min, &sec, &msec); 과 같이 사용하면 쉽게 정수를 추출할 수 있다.
Author And Source
이 문제에 관하여([Programmers 코딩 연습] [1차] 추석 트래픽 [Level 3]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@95kim2/Programmers-코딩-연습-1차-추석-트래픽-Level-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)