2021 kakao blind recruitment
문제 링크 :
https://programmers.co.kr/learn/courses/30/lessons/72414#fn1
내가 생각한 문제 풀이
[시도1]
우선 시간은 초로 환산해서 생각하는 것과, 시작 시간에만 최댓값이 갱신되기 때문에 이 부분만 보는 것을 아이디어로 잡았다. (비슷한 문제를 푼 적이 있음)
테케3을 처리하기 위해 함수 시작에 예외 처리를 해 주었고,
로그를 돌면서 초로 변환한 후 정렬해주었다.
정렬된 로그를 돌면서 내부 반복문으로 로그에 광고 시간이 포함되면 그 시간을 더해주었고, 가장 큰 값과 번호를 저장해 두었다.
시간 / 결과 / 패착
[시도1]
소요 시간 : 23
결과(정확도) : 3/31
오답 내용 : 시간 초과가 대부분이지만 그냥 오답도 있음
패착 :
문제 해설
[memozation]
킥 : 어차피 시간 최대로 해도 360000정도기 때문에 시간 자체를 배열으로 만들어두고 여기에 저장.
메모하는 기법
하나의 배열을 play_time길이만큼 설정한다.
1)logs를 돌면서 각 로그마다 start에 해당하면 +1 end에 해당하면 -1을 표기
이 때 배열은 시작하는 곳은 +1 끝나는곳은 -1을 기록한 배열이 된다
2)배열을 돌면서 arr[i] += arr[i-1]
이 때 배열은 해당 인덱스 초에 시청중인 사람의 수가 된다
3) 배열을 돌면서 한 번 더 arr[i] = arr[i]+arr[i-1]
이 때 배열은 0초부터 해당 인덱스 초까지 시청중인 사람의 수가 된다.
4) adv_time-1부터 play_time까지 for문을 돌면서 최대 view를 찾는다.
코드
def str2int(string):
hour, minute, second = string.split(':')
return int(hour) * 3600 + int(minute) * 60 + int(second)
def int2str(time):
hour = str(time // 3600).zfill(2)
time = time % 3600
minute = str(time // 60).zfill(2)
second = str(time % 60).zfill(2)
return hour + ':' + minute + ':' + second
def solution(play_time, adv_time, logs):
play_time = str2int(play_time)
adv_time = str2int(adv_time)
all_time = [0 for _ in range(play_time + 1)]
for log in logs:
start, end = log.split('-')
start = str2int(start)
end = str2int(end)
all_time[start] += 1
all_time[end] -= 1
maxtime = 0
starttime = 0
for i in range(1, len(all_time)):
all_time[i] = all_time[i] + all_time[i - 1]
for i in range(1, len(all_time)):
all_time[i] = all_time[i] + all_time[i - 1]
for i in range(adv_time - 1, play_time):
if i >= adv_time:
if all_time[i] - all_time[i - adv_time] > maxtime:
maxtime = all_time[i] - all_time[i - adv_time]
starttime = i - adv_time + 1
else:
if all_time[i] > maxtime:
maxtime = all_time[i]
starttime = i - adv_time + 1
return int2str(starttime)추가 공부
Memoization (메모이제이션)
dp(동적 계획법) 문제를 풀 때 흔히 쓰이는 방법.
문제의 정답이 입력값의 더 작은 부분에 대해 동일한 문제의 정답으로 구성되어 있는 문제
tip for me
str to int는 사용할 일이 많을 것 같았는데
int to str는 마지막에 답을 리턴할 때만 사용한다. 나는 이게 너무 귀찮아서
그냥 배열에다가 str값을 추가해서 붙여넣었다.
근데 이런 대충 사는 태도는 고치는게 좀 좋을 것 같다.
이건 걍 코딩테스트고 시간 초과만큼 메모리 초과가 잘 나지는 않지만
실제라면 그냥 함수 하나 더 쓰는게 이득이다.
대체 왜 코딩테스트에서 귀찮아하는 것인가..
고치셈
