프로그래머스 - 상담원 인원

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

 

1. 2023 현대모비스 알고리즘 경진대회 예선

문제 푸는데 하루를 썼다.

 

첫 구상은 상담원 배치를 재귀로 돌려 완전탐색 했다.

근데 시간 초과가 나서 product로 구했다.

각 상담원 배치 수를 이용해 계산을 진행한다.

 

1번 예제로 설명하면

(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 1)
(1, 2, 2)
(1, 2, 3)
(1, 3, 1)
(1, 3, 2)
(1, 3, 3)
(2, 1, 1)
(2, 1, 2)
(2, 1, 3)
(2, 2, 1) ................

 

이런 식으로 쭉쭉 경우의 수가 나온다.

여기서 합이 n이 되는 경우에만 계산을 진행한다.

(1, 2, 2) 또는 (2, 1, 2) 등이 있다.

 

그리고 상담원 타입에 따른 딕셔너리를 생성해 준다.

key는 상담 유형 value는 heapq가 들어간다.

heapq에는 상담이 끝나는 시간이 들어간다.

time_dic = {i+1:[] for i in range(k)}
        for i in time_dic.keys():
            heapq.heapify(time_dic[i])

 

time_dic의 value길이와 상담원 배치 수를 비교하여 더 데이터를 push 할 수 있는지 검사를 하고

push 못하면은 pop을 해서 겹치는 시간을 구해주고 새로운 시간을 push 해준다.

 

 

import heapq
from itertools import product
def solution(k, n, reqs):

    def cul(type_list):
        dept = 0
        time_dic = {i+1:[] for i in range(k)}
        for i in time_dic.keys():
            heapq.heapify(time_dic[i])

        for start_t, cun_t, cun_type in reqs:
            if len(time_dic[cun_type]) < type_list[cun_type-1]:
                heapq.heappush(time_dic[cun_type], start_t + cun_t)
            else:
                pop_time = heapq.heappop(time_dic[cun_type])
                if pop_time > start_t:
                    dept += pop_time - start_t
                    heapq.heappush(time_dic[cun_type], pop_time + cun_t)
                else:
                    heapq.heappush(time_dic[cun_type], start_t + cun_t)
        return dept

    answer = float('inf')
    for type_ in product(range(1, n-k+2), repeat=k):
        print(type_)
        if sum(type_) == n:
            answer = min(answer, cul(list(type_)))
    print(answer)
    return answer