[프로그래머스][KAKAO_BLIND][2019] 무지의 먹방 라이브

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

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

코딩테스트 연습

 

문제

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

코딩테스트 연습 - 무지의 먹방 라이브

 

내가 작성한 코드

def make_accu(times):
    accu = [times[0]]
    for time in times[1:]:
        accu.append(accu[-1] + time)
    return accu

def get_accu_order(times, accu, i, N):
    return accu[i] + times[i] * (N-i-1)

def bin_srch(times, accu, l, r, N, k):
    if r - l <= 1:
        if get_accu_order(times, accu, l, N) > k:
            return l
        return r

    mid = (r-l) // 2 + l
    val = get_accu_order(times, accu, mid, N)
    if val <= k:
        return bin_srch(times, accu, mid, r, N, k)
    elif val > k:
        return bin_srch(times, accu, l, mid, N, k)

def find_idx(last, k, limit, food_times):
    idx = k % last
    for i, time in enumerate(food_times):
        if time > limit:
            if idx == 0:
                return i+1
            else:
                idx -= 1

def solution(food_times, k):
    N = len(food_times)
    times = sorted(food_times)
    accu = make_accu(times)

    start = bin_srch(times, accu, 0, N, N, k)
    if start == N:
        return -1

    if start == 0:
        idx = find_idx(N, k, 0, food_times)
    else:
        idx = find_idx(N - start, k - get_accu_order(times, accu, start, N), times[start-1], food_times)

    return idx

• binary search
  
  • 특정값(인덱스)까지 누적 시간 정의
  • 좌측은 누적합, 우측은 현 인덱스의 값 기준 직사각형 값
  • K보다 작은 값을 binary search

요런 느낌

• N번 탐색
  • 나머지 K값에 대해, 다시 직사각형만큼 나눈 나머지로 인덱스 계산

 

다른 사람이 작성한 코드

def solution(ft, k):
    answer = 0

    while k > 0 :
        a = k // (len(ft) - ft.count(0) )
        b = k % (len(ft) - ft.count(0) )

        for i, j in zip(ft, range(len(ft))):
            if ft[j] != 0:
                ft[j] = i - a
                if ft[j] < 0:
                    b = b + abs(ft[j])
                    ft[j] = 0
            k = b

        if len(ft) - ft.count(0) ==0:
            return -1

        if k+1 <= len(ft) - ft.count(0):
            for i in ft:
                answer += 1
                if i !=0 :
                    k -= 1
                if k == -1:
                    return answer

• 완전탐색
  
  • 효율성 테스트가 있어서 완전탐색으로도 해결이 가능한지 몰랐다
  • 대신 위 코드는 140ms, 내 코드는 75ms로 시간을 반 정도로 줄일 수 있는 듯 하다

 

기억해야할 것

• 이런 복잡한 문제는 내가 푼 방식처럼 풀면 시간 안에 풀 수 없다
• 문제를 단순하하여 완탐으로라도 완성시키는게 우선인 듯 하다