카테고리 없음

[프로그래머스] 2019 카카오 블라인드 - 무지의 먹방 라이브

문제

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

 

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

 

programmers.co.kr

 

풀이

카카오 해설 (https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/)

K보다 커지게 되면 남은 시간의 개수로 나누지 않고 그때부터 while문을 돌다가 오버된 시간의 인덱스에서 반환하도록 했다.

근데 이렇게 했더니 몇몇 효율성 테스트에서 시간초과가 발생했다.

def find_order(time, sec, over): #기준 시간과 K를 넘긴 값을 받는다.
    for i in range(len(time)): #기준 시간보다 큰 값, 즉 다 소비되지 않은 음식만 남긴다.
        time[i] -= sec
        
    i = len(time)
    while(over > 0): #마지막인덱스부터 거꾸로 돌며 정확히 k초 일 때 반환한다.
        i -= 1
        if i < 0:
            i = len(time)-1
        if time[i] > 0:
            over -= 1
        
    return i
    
    ''' #while문으로 바꾸기 전 코드
    for i in range(len(time)-1, -1, -1):
        if time[i] > 0:
            over -= 1
        if over <= 0:
            return i
        if i == 0:
            i = len(time)-1
    
    #over가 0이 아닌데, 포문을 탈출한 경우 런타임 에러가 발생했었다. 포문의 인덱스 조작이 불가능한건가 싶다.
    '''

def solution(food_times, k):    
    foods = dict(enumerate(food_times))
    foods = sorted(foods.items(), key=lambda x : x[1])  #초와 순서를 묶어 정렬한다.ex)[(1,1),(2,2),(0,3)] 근데 그럴 필요 없었음 
    
    last_sec = 0
    left_foods = len(food_times)
    for order, sec in foods:
        k -= (sec-last_sec) * (left_foods)
        left_foods -= 1
        if k < 0: #만약 k초를 넘겨 계산했을 때
            return find_order(food_times, last_sec, abs(k)) + 1
        last_sec = sec

위의 코드는 효율성 테스트와 테스트케이스 16, 19, 20, 23번을 통과하지 못한 코드

 

그래서 sec를 찾은 후 오버된 시간만큼 반복문을 도는 대신,

오버되기 직전, 남은 시간을 인자로 넘겨 나머지 연산자와 인덱스로 답을 반환했다.

def find_order(time, sec, left_time):
    left_food = []
    for i in range(len(time)):
        time[i] -= sec
        if time[i] > 0:
            left_food.append(i) #음식이 남은 접시의 원래 순서를 저장
            
    return left_food[left_time%len(left_food)] #남은 음식수로 나누고 그 순서를 반환

def solution(food_times, k):
    foods = sorted(food_times)

    last_sec = 0
    left_foods = len(food_times)
    for sec in foods:
        k -= (sec-last_sec) * (left_foods)
        if k < 0:
            return find_order(food_times, last_sec, k + (sec-last_sec) * (left_foods)) + 1
        left_foods -= 1
        last_sec = sec
    
    return -1 #음식을 다 소비할때까지 오류가 발생하지 않았을 때 return -1

정확도 실패는 return -1때문이었다.

통과했다.

 

다른사람의 코드

 

볼 기력이 없다..

나중에 시간되면 추가해야지

 

 

cme10575