[프로그래머스][KAKAO_BLIND][2021] 광고 삽입

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

https://programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

 

내가 작성한 코드

from collections import deque

def time_to_int(time: str) -> int:
    time = list(map(int, time.split(':')))
    int_t = (time[0] * 3600) + (time[1] * 60) + time[2]
    return int_t

def int_to_time(int_t: int) -> str:
    time = ""
    for i in range(2, -1, -1):
        div, mod = divmod(int_t, 60 ** i)
        time += str(div).format().zfill(2) + ":"
        int_t = mod
    return time[:-1]

def solution(play_time, adv_time, logs):
    play = time_to_int(play_time)
    adv = time_to_int(adv_time)
    left_q = []
    right_q = []
    left = right = left_cnt = right_cnt = 0
    mx_watch = crnt_watch = mx_start = 0

    for s, e in map(lambda x: x.split('-'), logs):
        left_q.append((time_to_int(s), -1))
        left_q.append((time_to_int(e), 1))
        right_q.append((time_to_int(s), 1))
        right_q.append((time_to_int(e), -1))

    left_q = deque(sorted(left_q))
    right_q = deque(sorted(right_q))

    # right가 adv_time될 때까지 계산
    while right < adv:
        while right_q and right == right_q[0][0]:
            right_cnt += right_q.popleft()[1]
        crnt_watch += right_cnt
        right += 1
    mx_watch = crnt_watch

    # right가 play_time될 때까지 left/right 계산
    while right <= play:

        crnt_watch += right_cnt + left_cnt

        while right_q and right == right_q[0][0]:
            right_cnt += right_q.popleft()[1]
        while left_q and left == left_q[0][0]:
            left_cnt += left_q.popleft()[1]

        if mx_watch < crnt_watch:
            mx_watch = crnt_watch
            mx_start = left

        left += 1
        right += 1

    return int_to_time(mx_start)

• 투포인터로 완전 탐색
• 코드가 복잡하니까 이해하는 시간도, 버그 잡기도 매우 힘들다
• 포인터가 이동해야할 범위(< | <=), 계산 순서(현재값, 포인터 이동, 최대값 업데이트, 계산할 left/right의 count값 업데이트 등) 헷갈리는게 많다
  
  • 투포인터를 이용하는 문제들을 많이 풀어보면 좋을 것 같다

다른 사람이 작성한 코드

def solution(play, adv, logs):
    c = lambda t: int(t[0:2]) * 3600 + int(t[3:5]) * 60 + int(t[6:8])
    play, adv = c(play), c(adv)
    logs = sorted([s for t in logs for s in [(c(t[:8]), 1), (c(t[9:]), 0)]])

    v, p, b = 0, 0, [0] * play
    for t, m in logs:
        if v > 0:
            b[p:t] = [v] * (t - p)
        v, p = v + (1 if m else -1), t

    mv, mi = (s := sum(b[:adv]), 0)
    for i, j in zip(range(play - adv), range(adv, play)):
        s += b[j] - b[i]
        if s > mv:
            mv, mi = s, i + 1

    return f"{mi//3600:02d}:{mi%3600//60:02d}:{mi%60:02d}"

• 매우 간결하다
• for문은 내가 내용을 따라가기 힘들다
• 나도 사용해볼 수 있었을 법한 것들
  
  • 리스트 슬라이싱
    - split해서 인덱스 사용하는 것보다 보기 편한 것 같다
  • lambda를 이용한 간단한 함수 생성
    - def로 함수를 만들었는데 훨신 간결해보인다
  • f-string
    - 아직 관련 형식에 대해 명확하게 모르지만 간결해보인다

기억해야할 것

• zfill
  
  • "2".zfill(2) -> "02"로 만들어줌
• 투포인터 문제 풀이
  • 로직을 확실하게 잡아서 가져가자
    - 위에서 언급한 순서들의 배열이 꼬이면 정말 머리아프다