문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/72414?language=cpp
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
2021 카카오 블라인드 코딩 테스트에서 나온 문제
제한 시간을 두고 풀었을 때는, 감도 잡기 어려웠다.
처음에는 그리디처럼 생겨서 이리저리 정렬해 보다가 실패했다.
문제 핵심 및 풀이
누적합
누적합이라는 아이디어만 떠올리면, 해당 문제는 수월한데.. 떠올리기가 어렵다.
힌트를 얻을 수 있는 부분은 광고 누적 재생시간의 계산 방식이다.
임의에 시각에 시작해서 재생 시간 길이만큼 재생한다.
그때 각 시간에 걸쳐있는 log의 개수에 따라 배가 된다.
누적 재생 시간을 구한다는 것과,
각 시간에 걸쳐있는 log의 개수라는 것을 포인트로 잡는다.
각 시간에 걸쳐있는 log의 개수를 누적합으로 구할 수 있다.
예시
Play_Time = 10초
adv_time = 4초
A : 3 ~ 5초
B : 2 ~ 9초
C: 2 ~ 5초
시간마다 있는 숫자의 의미는 해당 시간의 변화한 log의 수를 뜻한다.
이는 아래에 A, B, C를 적용한 것을 보면 이해될 것이다.
각 log의 시작 시간마다 1 증가하고, 종료 시간마다 1 감소한다.
3번 상태를 보면 2초에 log의 변화가 2개 있다는 것을 알 수 있다.
이제 이를 누적합을 하면, 각 시간마다 가지고 있는 log의 개수를 알 수 있다.
이런 식의 결과가 나온다.
예를 들어, 4초 때는 3개의 log가 있다는 것이다.
하지만 구해야 하는 것은 각 시간마다 개수가 아닌,
광고 재생 시간의 누적 재생 시간이다.
각 시간마다 log가 몇 개 있는지 구했으니까,
출발 시간을 잡고, 광고 재생 시간 길이에 맞춰 구하면 된다.
근데, logs의 최대 길이가 300,000이기 때문에
출발 지점을 하나하나 잡고 구하면 O(N^2)이다.
따라서 이를 구하기 위한 다른 방법이 필요하다.
그래서 한번 더 누적합을 통해 구하는 법을 사용한다.
모든 출발 지점을 0초로 잡고,
광고 재생 시간이 1초부터 playTime까지 순차적으로 구해보자.
여기서 의미를 잘 파악해야 하는데,
광고 재생 시간이 1초이고, 시작 지점을 2초로 한다고 가정하자.
범위는 2초 ~ 3초지만, 여기서 3초는 포함되지 않는다.
왜냐하면 n초를 온전히 사용했을 때의 값을 뜻하기 때문이다.
2초에서 시작하면 log의 개수는 2개가 된다.
그리고 2에서 3초로 넘어가는데 1초를 이미 소비했으므로, 3초에 있는 값은 얻을 수 없다.
결론적으로 끝나는 시간은 포함되지 않는다는 것을 유의해야 한다.
이제 한번 구해보자.
시작 지점을 4초로 잡고, 광고 재생 시간이 4초라면
4 ~ 8초이다. 여기서 8초는 포함되지 않으므로
map [8-1] - map [4-1] 이다.
여기서 map [4-1]은 여기서 map [4]가 빠져버리면,
4초일 때의 누적값을 얻을 수 없기 때문이다.
빼야 하하는 것은 0 ~ 3초 일 때의 값이기 때문에 1을 빼준다.
이런 식으로 0초부터 시작하여
playTime까지 위 식을 적용시켜 값이 가장 클 때의 시작 지점이 답이 된다.
여기서 이 식을 일반화 해보자.
광고 재생 시간을 aTime으로 하고,시작 시간이 k이다.
자연스럽게 광고 종료 시간은 k + aTime이 된다.
answer [k] = map [k+aTime-1] - map [k-1]
이렇게 된다.
나머지 부분에 대해서는 따로 언급하지 않았는데,
그냥 구현적인 부분이기 때문에 코드에서 보면 된다.
입력의 시간을 파싱 하여 시와 분을 모두 초로 바꿔주는 것으로 단위를 통일해 줬다.
이제 이를 코드로 잘 구현해 보면 된다.
실수하기 쉬운 부분
한 가지 함정이 있는데, 누적합을 하는 과정에서 int의 범위를 넘어간다.
그래서 누적합을 담는 자료형을 long형으로 해줘야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
// 문자열을 받아 초 단위로 바꿔서 반환
int toSeconds(string times){
istringstream ss(times);
string buf = "";
int t[3];
int idx = 0;
while(getline(ss,buf,':')){
t[idx++] = stoi(buf);
}
return t[0]*3600 + t[1] * 60 + t[2];
}
// 초로 된 시간을 받아서 정답 출력 포맷을 반환
string toFormatted(int times){
int hours = times / 3600;
int minutes = (times % 3600) / 60;
int seconds = (times % 3600) % 60;
// 2자리가 넘어가지 않으면 앞에 0을 추가한다.
string h =(hours > 9)? to_string(hours) : "0"+to_string(hours);
string m =(minutes > 9)? to_string(minutes) : "0"+to_string(minutes);
string s =(seconds > 9)? to_string(seconds) : "0"+to_string(seconds);
return h + ":" + m+ ":"+s;
}
string solution(string play_time, string adv_time, vector<string> logs) {
// 광고시간 길이와 재생시간을 모두 초로 바꿔줌
int adTime = toSeconds(adv_time);
int playTime = toSeconds(play_time);
string answer = "";
// playTime + 1의 범위를 가지도록 한다.(초 단위로 받기 위해)
vector<long> times(playTime+1,0);
for(auto log : logs){
int sTime = toSeconds(log.substr(0,8)); // 시작 시간
int eTime = toSeconds(log.substr(9)); // 종료 시간
times[sTime]++; // 시작 초 + 1
times[eTime]--; // 종료 초 - 1
}
// 누적합을 2번 수행해야하기 때문
// 첫번째 반복 = 각 초의 log의 개수 구하기
// 두번째 반복 = 0초를 시작지점으로 했을 때 광고 누적 재생 시간
for(int k = 0; k < 2; k++){
for(int i = 1; i <= playTime; i++){
times[i] += times[i-1];
}
}
// 0 ~ adTime을 시작값을 잡음
long sum = times[adTime-1]; // 자료형 long
int ansTime = 0; // 시작 정답 시간
for(int i = 0; i <= playTime-adTime; i++){
long cnt = times[i+adTime-1]-times[i-1];
// 값이 더 클때만 갱신
if(cnt > sum){
sum = cnt;
ansTime = i;
}
}
// 구한 시간을 포맷화
answer = toFormatted(ansTime);
return answer;
}
Java 구현 코드
↓
import java.util.*;
class Solution {
long[] times; // 자료구조 long, 각 초의 누적시간을 담을 배열
public String solution(String play_time, String adv_time, String[] logs) {
int adTime = toSeconds(adv_time);
int playTime = toSeconds(play_time);
times = new long[playTime+1];
Arrays.fill(times,0);
for(String log : logs){
String[] splited = log.split("-");
times[toSeconds(splited[0])]++;
times[toSeconds(splited[1])]--;
}
// 각 초의 log의 개수 구하기
for(int i = 1; i <= playTime ; i++){
times[i] += times[i-1];
}
// 0초를 시작지점으로 했을 때 광고 누적 재생 시간
for(int i = 1; i <= playTime; i++){
times[i] += times[i-1];
}
int sTime = 0; // 시작 정답 시간
// 0 ~ adTime을 시작값을 잡음
long ansTime = times[adTime-1];
for(int i = 1; i <= playTime-adTime;i++){
// 값이 더 클때만 갱신
if(times[i+adTime-1] - times[i-1] > ansTime){
ansTime = times[i+adTime-1] - times[i-1];
sTime = i;
}
}
// 구한 시간을 포맷화
return toFormatted(sTime);
}
// 문자열을 받아 초 단위로 바꿔서 반환
public int toSeconds(String time){
String[] splited = time.split(":");
int hours = Integer.parseInt(splited[0]);
int minutes = Integer.parseInt(splited[1]);
int seconds = Integer.parseInt(splited[2]);
return hours * 3600 + minutes * 60 + seconds;
}
// 초로 된 시간을 받아서 정답 출력 포맷을 반환
public String toFormatted(int time){
int hours = time / 3600;
int minutes = (time % 3600) / 60;
int seconds = (time % 3600) % 60;
// 2자리가 넘어가지 않으면 앞에 0을 추가한다.
return String.format("%02d:%02d:%02d",hours,minutes,seconds);
}
}↑
시행착오
집에서 혼자 천천히 생각했는데, 그래도 답을 생각 못했다.
풀이를 보고 나서 알았다. 누적합을 생각하지도 못했다.
누적합으로 된 문제 자체를 오랜만에 풀어봤다.
정답률 낮을만하네;
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me