문제 설명 :
https://school.programmers.co.kr/learn/courses/30/lessons/72414
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 요약:
- 최대의 광고 효과를 얻을 수 있는 광고 시작 시간 구하기
문제 풀이 시간 : 2시간
문제 성공 여부 : 실패
접근 방법(실패):
- 누적합을 사용하여 각 시간 별 광고 출력 시간 구하기
- 0초부터 시작하여 99시59분59초까지 광고 시작 시간에 대한 총 광고 출력 시간 구하기
처음에 그리디 방식으로 풀어보려고 하였으나, 아무리 생각해도 30만 개의 서로 다른 시간에 대해 최대 광고 출력 시간을 구할 수 없었다고 판단하였다.
따라서, 누적합을 통해 각 시간별 최대 광고 출력 시간을 저장하면 시간에 대한 문제는 해소될 것으로 판단하였다.
구현을 하기 전, 먼저 시간, 공간 복잡도가 충분하지에 대해 계산해보았다.
시간 복잡도
필요한 시간은 최대 360000이다.
30만개의 logs를 읽으며 시작시간와 종료시간에 각각 +1, -1를 해준다. (누적합 갱신을 위해) (총 300,000 탐색)
이후 누적합 갱신을 해주며, 현재 시간대에 몇개의 티비가 동시 시청하고 있는지를 갱신해준다. (총 360,000 탐색)
이제, 다시 누적합을 갱신해주며, 현재 시간대에 총 몇초의 광고 수익 효과가 나올 수 있는지를 갱신해준다 (총 360,000 탐색)
마지막으로, 갱신된 누적합에 대해 최대 광고 수익 효과를 구해야한다.
0초부터 시작 시간과, 시작시간에 광고시간(adv-time)을 더한 종료 시간을 구해주고,
종료시간 - 시작 시간을 하여 시작 시간에 얻을 수 있는 광고 효과를 O(1)만에 구해줄 수 있다. (총 360,000 탐색)
결과적으로 최대 1,000,000 언저리의 최악의 시간이 나오므로 시간 복잡도는 크게 고려할 필요가 없어보인다.
공간 복잡도
사실 이 부분에서 누적합 방식을 꽤 오랫동안 고민하게 만들었다.
0초부터 최대 시간인 99시59분59초까지 모든 초단위로 배열을 구성하게 되면 약 360,000개의 공간이 필요해진다.
프로그래머스에서 메모리를 얼마나 사용할 수 있는지 모르기에 고민되었으나, int 배열 기준 360,000 공간을 할당하면 약 1MB이다.
문제가 없길 바라며 누적합 방식을 시도하였다.
로직
1. 문자열 시간을 정수로 변환 함수
static int StringToInt(String time){
String hour = time.substring(0,2);
String min = time.substring(3,5);
String sec = time.substring(6,8);
int h = Integer.parseInt(hour);
int m = Integer.parseInt(min);
int s = Integer.parseInt(sec);
int result = h*3600 + m*60 + s;
return result;
}
시간 문자열을 받으면, 시,분,초를 잘라서 parseInt 메서드로 변환해준다.
이후 초 단위로 시간을 계산하여 반환해준다
ex) 01:02:03 -> 1*3600 + 2*60 + 3 = 3723
2. 정수 시간을 문자열 시간으로 변환 함수
static String IntToString(int time){
long[] t = new long[3];
t[0] = time / 3600;
t[1] = (time % 3600) / 60;
t[2] = (time % 3600) % 60;
StringBuilder sb = new StringBuilder();
for(int i = 0; i<3; i++){
if(t[i] < 10){
sb.append('0').append(t[i]);
}
else{
sb.append(t[i]);
}
if(i<2) sb.append(':');
}
return sb.toString();
}
마지막에 구하게 된 최대 광고 시간을 다시 문자열로 변환해 주는 함수이다.
시, 분, 초로 나누어 만약 10보다 작을 경우(한 글자일 경우) 0을 붙여준다.
3. 누적합 갱신
int[] sum = new long[LIMIT_TIME+2];
for(int i=0; i<logs.length; i++){
String log = logs[i];
StringTokenizer st = new StringTokenizer(log, "-");
String from = st.nextToken();
String to = st.nextToken();
int f = StringToInt(from);
int t = StringToInt(to);
sum[f] += 1; // 누적합 설정
sum[t] -= 1;
}
for(int i = 1; i<sum.length; i++){ // 첫 번째 누적합 갱신
sum[i] = sum[i] + sum[i-1];
}
for(int i = 1; i<sum.length; i++){ // 두 번째 누적합 갱신
sum[i] = sum[i] + sum[i-1];
}
복잡해 보이지만, 아주 별 거 없다.
log를 시작시간, 종료시간 정수로 변환하여, 해당 시간대의 누적합에 +1, -1을 갱신해준다.
이후 첫번째 누적합 갱신을 해주어, 각 시간 별 시청하고 있는 시청자 수를 구해준다.
이후 두번째 누적합 갱신을 통해, 각 시간 별 얻을 수 있는 광고 시간을 갱신해준다.
ex) 1초~6초, 3초~8초 시청자가 있을 경우
시간대 : 0 1 2 3 4 5 6 7 8 9 초
누적합 : 0 1 0 1 0 0 -1 0 -1 0 // 시작시간, 종료시간에 +1, -1을 해준다
누적합 : 0 1 1 2 2 2 1 1 0 0 // 각 시간대 별 시청자 수를 갱신
누적합 : 0 1 2 4 6 8 9 10 10 10 // 각 시간대 별 총 광고 시간을 갱신
결과적으로 s초의 광고 수익 효과를 알기 위해서는,
sum[s+edv-1] - sum[s-1]을 해주면 s초에 광고를 시작하였을 때의 광고 시간을 구할 수 있게된다!
4. 각 시작 시간에 따른 광고 시간 구하기
int adv = StringToInt(adv_time); // 광고시간 (정수)
int max_time = sum[adv-1]; // 0초에 얻을 수 있는 광고 시간
int ans_time = 0; // 광고 시작 시간(정답)
for(int s = 1; s<LIMIT_TIME+1-adv; s++){ // 시작할 수 있는 모든 시작 시간 탐색
int e = s+adv; // 광고 끝나는 시간
int total_time = sum[e-1] - sum[s-1]; // 해당 간격에 얻을 수 있는 시간
if(max_time < total_time){ // 최대값 갱신
ans_time = s;
max_time = total_time;
}
}
완벽하게 했다고 생각했는데, 17번 케이스만 오답이 나왔다..
아무리 생각해봐도 답이 안나와서 결국 주어진 시간 1시간에서 1시간을 더 쓰고도 찾지 못하였다.
실패 원인
0초~99시59분59초가 30만개 들어오는 케이스를 생각해보자.
sum 배열의 두 번째 누적합 갱신에서 어떻게 될까?
300,000 600,000 1,200,000, .... overflow
접근 방법(성공) :
오버플로우 방지를 위해, 누적합 배열을 long 타입으로 변경하였고 드디어 정답이 나왔다!
import java.util.*;
class Solution {
static int LIMIT_TIME = 99*3600 + 59*60 + 59;
public String solution(String play_time, String adv_time, String[] logs) {
long[] sum = new long[LIMIT_TIME+2];
for(int i=0; i<logs.length; i++){
String log = logs[i];
StringTokenizer st = new StringTokenizer(log, "-");
String from = st.nextToken();
String to = st.nextToken();
int f = StringToInt(from);
int t = StringToInt(to);
sum[f] += 1;
sum[t] -= 1;
}
for(int i = 1; i<sum.length; i++){
sum[i] = sum[i] + sum[i-1];
}
for(int i = 1; i<sum.length; i++){
sum[i] = sum[i] + sum[i-1];
}
int adv = StringToInt(adv_time);
long max_time = sum[adv-1];
int ans_time = 0;
for(int s = 1; s<LIMIT_TIME+1-adv; s++){
int e = s+adv;
long total_time = sum[e-1] - sum[s-1];
if(max_time < total_time){
ans_time = s;
max_time = total_time;
}
}
String answer = IntToString(ans_time);
return answer;
}
static int StringToInt(String time){
String hour = time.substring(0,2);
String min = time.substring(3,5);
String sec = time.substring(6,8);
int h = Integer.parseInt(hour);
int m = Integer.parseInt(min);
int s = Integer.parseInt(sec);
int result = h*3600 + m*60 + s;
return result;
}
static String IntToString(long time){
long[] t = new long[3];
t[0] = time / 3600;
t[1] = (time % 3600) / 60;
t[2] = (time % 3600) % 60;
StringBuilder sb = new StringBuilder();
for(int i = 0; i<3; i++){
if(t[i] < 10){
sb.append('0').append(t[i]);
}
else{
sb.append(t[i]);
}
if(i<2) sb.append(':');
}
return sb.toString();
}
}
앞으로 오버플로우를 꼭 생각해보는 습관을 들여야 할 것 같다.
'코테 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 다음 큰 숫자 - java (2) | 2025.04.07 |
|---|---|
| [프로그래머스] 도둑질 - java (4) | 2025.04.03 |
| [프로그래머스] 양과 늑대 - java (1) | 2025.03.27 |
| [프로그래머스] 봉인된 주문 - java (1) | 2025.03.26 |
| [프로그래머스] 이모티콘 할인 행사 - java (1) | 2025.03.23 |