Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 완전탐색
- 수학
- 투 포인터
- 유니온 파인드
- CS
- 위상정렬
- 알고리즘
- 세그먼트 트리
- 후니의 쉽게 쓴 시스코 네트워킹
- java
- swea
- 동적계획법
- dfs
- 백트래킹
- 백준
- JUnit 5
- Effective Java
- Kotlin
- 프로그래머스
- 에라토스테네스의 체
- 문자열
- 시뮬레이션
- mst
- 그리디
- 구현
- BFS
- 이분탐색
- 플로이드-와샬
- Network
- 스택
Archives
반갑습니다!
[프로그래머스] 추석 트래픽 본문
풀이
모든 시간을 millisec 단위로 변환하여 해결하였다. 문제는 1초간 처리하는 최대 갯수를 구하는 것이다. 입력값을 계산해서 시작 시간과 완료 시간을 구할 수 있는데, millisec로 변환했기 때문에 초 단위의 트래픽 처리량을 체크하기위한 별도의 처리를 해줘야한다.
예를 들어 13시 21분 3.001초에 1초간 트래픽 처리를 시작했다면 13시 21분 3초부터 4초까지 실시했다는 것을 알 수 있다. 이번에는 13시 21분 3.012초에 1초간 트래픽 처리를 했다면 13시 21분 3초부터 13시 21분 5초까지 트래픽 처리가 되었다고 볼 수 있는 것이다. 따라서 처리 끝 시간을 millisec 단위로 바꾸게 되면 999를 더해 범위를 조정해야한다.
millisec로 시작 시간과 완료 시간을 구하게 되면 배열을 통해 처리를 표시하고, 최대값을 구하면 정답을 찾을 수 있다.
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int chk[60 * 60 * 24 * 1000 + 1];
struct Time {
int h, m, s, ss;
};
// 처리 시간을 millisec로 변환해주는 함수
int get_millisec(string millisec) {
int ret = 0;
if (millisec.find('.') == string::npos) return stoi(millisec.substr(0, 1)) * 1000;
for (int i = 0; i < millisec.length(); i++)
if (millisec[i] == '.') {
ret += stoi(millisec.substr(0, 1)) * 1000;
ret += stoi(millisec.substr(i + 1));
break;
}
return ret;
}
// 처리가 끝난 시간을 int로 변환해주는 함수
Time parse_lines(string str) {
int h = stoi(str.substr(11, 2));
int m = stoi(str.substr(14, 2));
int s = stoi(str.substr(17, 2));
int ss = stoi(str.substr(20, 3));
return { h, m, s, ss };
}
int solution(vector<string> lines) {
int answer = 0;
for (string str : lines) {
// 시간을 millisec 단위로 변경
Time t = parse_lines(str);
int h = t.h * 60 * 60 * 1000;
int m = t.m * 60 * 1000;
int s = t.s * 1000;
int ss = t.ss;
int pt = get_millisec(str.substr(24));
// 끝나는 시간을 millisec로 구한다
int last = h + m + s + ss;
// 시작한 시간을 구한다.
int first = last - pt + 1;
// 초 단위 답을 구하기 위해 999를 더해준다
last += 999;
// 0보다 작으면 9월 14일이 되므로 9월 15일 00시 00분 00초로 변경
if (first < 0) first = 0;
// 최대 범위를 벗어나면 최대값으로 변경
if (last > 24 * 60 * 60 * 1000) last = 24 * 60 * 60 * 1000;
// 범위 내 값 증가
for (int i = first; i <= last; i++)
chk[i]++;
}
for (int i = 0; i <= 24 * 60 * 60 * 1000; i++)
answer = max(answer, chk[i]);
return answer;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 15683 감시 (0) | 2020.05.11 |
---|---|
[프로그래머스] 불량 사용자 (0) | 2020.05.09 |
[백준] 14891 톱니바퀴 (0) | 2020.05.08 |
[백준] 14890 경사로 (0) | 2020.05.08 |
[프로그래머스] 셔틀버스 (0) | 2020.05.07 |