생각해보면 고려해야 할 전체 범위가 크지 않아서 배열로 만들기에 괜찮다.
문제 풀이 단계
1) 각 logs를 초 단위로 바꾼다. 그리고 시작 시간부터 끝 시간까지의 초를 배열에 1씩 저장한다.
2) 0부터 (adv_time-1)까지의 배열 값을 다 더한다.
3) adv부터 play_time까지 보면서, 1씩 늘려간다. 그리고 1씩 늘리는 만큼 앞에서 1씩 줄인다. 딱 adv만큼의 배열칸 값을 저장하도록 한다.
=> (0,i) 범위로 더했으면, 그 다음은 (1,i+1) 범위로 더한다. 즉, (i+1) index의 배열 값은 더하고, 0 index의 배열 값은 뺀다.
4) 만약, 가장 큰 누적 재생시간이 나타나면 초기화 하고, 그 시간이 시작된 초 값을 저장한다.
예전에 비슷한 문제를 풀 때, vector에 (a,b),(c,d)가 있으면 c가 b보다 작을 경우 어쩌구저쩌구 하란 풀이였는 게 기억났다. (자세히 기억 안 나는 건 ㄹㅈㄷ)
그래서 그 방법으로 하다가 예전에 푼 코드를 봤는데, 그게 아니였다...!
(그 문제는 추석 트랙픽 문제다. 이것도 좋은 문제~)
99:99:99까지 가능하다는 조건을 보고 '에이 배열은 무조건 안 되지'라면 속단했던 게 못푼 근본적인 원인 같다.
100시간이라고 해봤자 초로 바꾸면 360000이다. 충분히 배열을 만들 수 있다.
사실 이렇게 할 수 있단 걸 알아도 답을 찾는 과정은 쉽지 않았다.
머리가 빡대가리라서 그런 걸까...?
다음 한 칸을 더했으니, 앞의 한 칸은 빼줘야 하는 건 당연한데 이걸 구현 못해서 엄청 헤맸다... 제발 발전 쿠다사이...!!!
#include <string>
#include <vector>
#define ll long long
#define limit 360000
using namespace std;
int arr[limit];
// toInt -> 문자열을 int로(==초 단위로)
int toInt(string time){
int h=stoi(time.substr(0,2));
int m=stoi(time.substr(3,5));
int s=stoi(time.substr(6));
return h*60*60+m*60+s;
}
// toString -> int를 문자열로(==HH:MM:SS 이런 형식으로)
string toString(int time){
string h=to_string(time/3600);
h= h.length()==1 ? "0"+h : h;
time%=3600;
string m=to_string(time/60);
m= m.length()==1 ? "0"+m : m;
time%=60;
string s=to_string(time);
s= s.length()==1 ? "0"+s : s;
return h+":"+m+":"+s;
}
string solution(string play_time, string adv_time, vector<string> logs) {
string answer = "";
int adv=toInt(adv_time);
for(int i=0; i<logs.size(); i++){
int start=toInt(logs[i].substr(0,8)), end=toInt(logs[i].substr(9));
// 누적합을 해준다.
for(int j=start; j<end; j++) arr[j]++;
}
// sum: 누적합, ans: 시작 시간, mx: 최대 누적시간
ll sum=0, ans=0, mx=0;
for(int i=0; i<adv; i++) sum+=arr[i];
mx=sum;
for(int i=adv; i<limit; i++){
sum+=arr[i]-arr[i-adv];
if(mx<sum) {
mx=sum;
ans=i-adv+1;
}
}
return answer=toString(ans);
}
누적합이라고 생각도 못했다... 이전에 푼 코드를 보고 누적합인 걸 알았을 때
아 헐
이 생각만 들었다...
누적합은 때때로 나오는 문제다. 과거를 되짚어보면 늘 누적합 문제를 풀 때 끙끙 앓다가 아 헐
을 외쳤는 것 같다.
좋은 문제지만, 오마카세라고 할 만큼 삘이 안 와서 준오마카세로 분류했다.
TMI지만, 내일은 처음은 오마카세를 먹으러 간다. 야호!