무지의 먹방라이브

2019 카카오 신입 공채

무지의 먹방라이브

# 20210125
# CHAPTER11 Greedy
# Q06 무지의 먹방라이브
# 먹어야 할 음식 N개
# K ~ K+1 초에 먹을 음식 번호는?

import sys
sys.stdin = open("input.txt", "r")

def solution(food_times, k):
    answer = -1

    size_list = sorted(list(set(food_times)))
    number_of_sizes = [0] * (size_list[-1] + 1)
    for n in food_times:
        number_of_sizes[n] += 1
    # print(number_of_sizes)

    # 누적배열만들기
    for idx in range(len(size_list) - 1, 0, -1):
        number_of_sizes[size_list[idx - 1]] += number_of_sizes[size_list[idx]]
    # print(number_of_sizes)

    # 한턴씩 음식먹기 (한턴 : 남은 음식을 모두 먹으려 시도하고 가능하면 먹고 다음턴, 불가능하면 거기에 정답존재)
    prev_size = 0
    for size in size_list:
        # 가능한 경우 먹는다 (k초 소요)
        if k >= (number_of_sizes[size] * (size - prev_size)):
            k -= (number_of_sizes[size] * (size - prev_size))
            prev_size = size
        # 불가능한 경우 정답존재
        else:
            # 남은 음식 중 몇번째가 정답인지 cnt로 확인
            cnt = (k+1) % number_of_sizes[size]
            # cnt가 0인 경우는 k>=0이므로 남은 음식 수 == cnt 일때 위의 연산에서 0이 되는 경우 뿐
            if cnt == 0:
                cnt = number_of_sizes[size]
            # print(cnt)
            # 남은 음식 중 cnt 번째의 음식 찾기
            for idx in range(len(food_times)):
                if food_times[idx] >= size:
                    cnt -= 1
                    # print('cnt = ' + str(cnt) + 'idx = ' + str(idx))
                    if cnt <= 0:
                        answer = idx + 1
                        return answer

    # 위의 for문을 모두 돌고났는데 return 되지 않았다는 것은 남은 음식이 없는 경우이다. (-1 반환)
    return answer

K = int(input())
input_list = list(map(int, input().split()))
print(solution(input_list, K))