[프로그래머스] 광고 삽입 - 2021 KAKAO BLIND RECRUITMENT

파닥몬·2022년 9월 20일
0

KAKAO를 풉니다.

목록 보기
9/12
post-thumbnail

⚙️ 알고리즘 분류 : 누적합

🔠 언어 : c++

🤫 힌트.

생각해보면 고려해야 할 전체 범위가 크지 않아서 배열로 만들기에 괜찮다.

✏️ 풀이.

문제 풀이 단계
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지만, 내일은 처음은 오마카세를 먹으러 간다. 야호!

profile
파닥파닥

0개의 댓글