[SWEA]2477.차량정비소 (python)

문제 설명

구현문제이다. 대기하는 줄이 존재하고 서비스하는 카운터가 존재한다.

전형적인 queue문제.

삼성의 구현문제인 만큼 차근차근히~ 읽어서 풀어야 한다.

주어진 자료는 다음과 같다.

1. 고객이 차량 정비소에 도착한 순서대로 번호를 부여받는다.
2. 접수창구가 꽉차있으면 도착 순으로 대기하고, 접수창구가 비어있으면 비어있는 창구 중 번호가 빠른 접수창구로 이동한다.
3. 정비창구도 이와 같이 도착순, 번호가 빠른, 비어있는 창구로 이동한다.
   하지만! 동시에 접수창구가 서비스가 끝났을 경우 번호가 빠른 접수창구가 우선적으로 정비를 받는다.

문제의 목적은 특정 창구를 이용했던 사람들 찾는 것이다.(정확히는 그 사람들의 합)

접근

어떻게 하면 문제를 단순하게 볼 수 있을까?

큐

결국~ 대기행렬이론에서 큐1개, 서비스하는 곳 1개(server 여러명 존재)를 고려한 것인데, 이게 2개 있는거라고 보면 된다.

어떻게 잘 다형성을 이용하면 매우~ 깔끔한 코드가 완성될 수 있다. 규칙이 거의 동일하므로.

평소했던 큐문제와 비슷하게 접근하면 되겠다.

시간

시간의 흐름을 어떻게 설정해주어야 될까? [카카오-무지의 먹방],[프로그래머스-CPU스케줄링] 문제는 서비스가 남아있는 시간만을 고려한다. 매초마다 진행상황을 초기화시켜주는 식으로 코딩하면 시간초과가 된다.

하지만 이 문제는 시간이 최대 1000초로 충분히 1초씩 확인이 가능하다. 큐 부분에서도 서비스완료시간, 서버의 최대 수를 보면 오래걸리지 않을 것이라 생각된다.

프로세스

그렇다면 시간에 대한 프로세스를 다음과 같이 짤 수 있다.

1. 시간은 매초마다 흐른다.

위와 같은 상황에서 큐는 어떻게 짤 수 있을까?

• queue먼저 서비스로 이동시킨다.
  • 서비스받고 나가야할 사람을 고려하지 못하므로 잘못됬다.
• 위와 같은 이유로 서비스 먼저 시간이 흐르는 것으로 코딩을 해야한다.
• 그렇다면 접수창구 큐 , 정비창구 큐 중 어디먼저 고려해도 상관이 없을까?
  • 상관없다. 이미 서비스를 받은 사람을 고려했다면 채워야 할 큐는 더이상 없다. 영향을 받지 않으므로 임의의 창구 먼저 한다.

따라서 큐에 대한 프로세스를 상세히 구현하면 다음과 같다.

1. 서비스 쪽에 남은 시간을 1씩 모두 줄인다.
2. t초때 올 사람들을 reception 큐에 넣는다.
3. 접수창구에서 남은 서비스 시간이 0초인 사람은 정비 창구 큐에 넣는다.
   • 이때 반드시 접수창구에서 남은 시간을 오름차순으로 고려해야 한다. 큐는 선입선출으로, 접수 창구가 낮은 번호가 먼저 서비스를 받아야 하므로.
4. 정비창구에서 남은 서비스 시간이 0인 사람은 접수창구번호, 정비창구번호를 고려하여 문제의 목표에 부합하다면 더해준다.

큐의 원소

큐의 원소는 쉽게 이해하기 위해 서비스 남은 시간, 어디 창구에서 받았는지 알 수 있는 필드를 가지고 있도록 했다.

시간 복잡도

이에 따라 시간 복잡도는

(특정 시간에 사람이 오는 것 pop해주는 연산 + 접수 창구 수(n) 1초 줄이는 연산 + 정비창구 1초 줄이는 연산 + 접수큐 pop 연산 + 정비창구 pop연산 + 문제 목표에 맞는지 확인 해주는 연산 ) * 최대 흐른 시간

으로, 대략 최악의 경우 (1000 + 9 + 9 + 1000 + 1000 + 9) * T [ k<=1000, n,m<=9]

이라 볼 수 있다.

pop해주는 연산도 1000번까지 해버리면 종료되버리니까 오버한 수치라 볼 수 있다.

T는 최악의 경우 사람 1000명, 접수,정비창구 1개, 서비스시간 20으로 20020이라 볼 수 있는데

위에서 접수창구 수 9개인 경우로 봤으므로 이보다는 적을 것이다.

따라서 대략 3000*20000 = 60,000,000

연산횟수는 실제 문제 최대를 상회하는 수인 6천만이다.

그런데 문제의 조건에서 C++은 3초이므로 충분히 시간 내 풀이가 가능하다!

구현

import collections

testCase = int(input())


class Customer:
    def __init__(self):
        self.customerNumber = None
        self.receptionNumber = None
        self.maintenanceNumber = None
        self.remainProcessingTime = None

    def setCustomerNumber(self, n):
        self.customerNumber = n

    def setReceptionNumber(self, n):
        self.receptionNumber = n

    def setMaintenanceNumber(self, n):
        self.maintenanceNumber = n

    def setRemainProcessingTime(self, t):
        self.remainProcessingTime = t

    def getCustomerNumber(self):
        return self.customerNumber

    def getReceptionNumber(self):
        return self.receptionNumber

    def getMaintenanceNumber(self):
        return self.maintenanceNumber

    def getRemainProcessingTime(self):
        return self.remainProcessingTime

def findCounter(counter,x):
    for i in range(1,x+1):
        if counter[i] != 0:
            return True
    return  False

def comeInReceptionQueue(t, comeInTime, receptionQueue, k):
    while comeInTime and comeInTime[0] == t:
        k += 1
        customer = Customer()
        customer.setCustomerNumber(k)
        receptionQueue.appendleft(customer)
        comeInTime.popleft()
    return k


def proccessReceptionCounter(receptionCounter, receptionQueue, maintenanceQueue, receptionCounterProcessingTime, n):
    for i in range(1, n + 1):
        if receptionCounter[i] != 0:
            customer = receptionCounter[i]
            customerRemainTime = customer.getRemainProcessingTime()
            customerRemainTime -= 1

            # 딱 0이 되면!
            if customerRemainTime == 0:
                maintenanceQueue.appendleft(customer)
                if receptionQueue:
                    addedCustomer = receptionQueue.pop()
                    addedCustomer.setReceptionNumber(i)
                    addedCustomer.setRemainProcessingTime(receptionCounterProcessingTime[i])
                    receptionCounter[i] = addedCustomer
                else:
                    receptionCounter[i] = 0
            else:
                customer.setRemainProcessingTime(customerRemainTime)

        else:
            if receptionQueue:
                addedCustomer = receptionQueue.pop()
                addedCustomer.setReceptionNumber(i)
                addedCustomer.setRemainProcessingTime(receptionCounterProcessingTime[i])
                receptionCounter[i] = addedCustomer
            else:
                receptionCounter[i] = 0


def proceessMaintenanceCounter(maintenanceCounter, maintenanceQueue, maintenanceCounterProcessingTime, m, a, b, answer):
    for j in range(1, m + 1):
        if maintenanceCounter[j] == 0:
            if maintenanceQueue:
                addedCustomer = maintenanceQueue.pop()
                addedCustomer.setMaintenanceNumber(j)
                addedCustomer.setRemainProcessingTime(maintenanceCounterProcessingTime[j])
                maintenanceCounter[j] = addedCustomer
            continue

        customer = maintenanceCounter[j]
        customerRemainTime = customer.getRemainProcessingTime()
        customerRemainTime -= 1

        if customerRemainTime == 0:
            if customer.getReceptionNumber() == a and customer.getMaintenanceNumber() == b:
                answer += customer.getCustomerNumber()

            if maintenanceQueue:
                addedCustomer = maintenanceQueue.pop()
                addedCustomer.setMaintenanceNumber(j)
                addedCustomer.setRemainProcessingTime(maintenanceCounterProcessingTime[j])
                maintenanceCounter[j] = addedCustomer
            else:
                maintenanceCounter[j] = 0
        else:
            customer.setRemainProcessingTime(customerRemainTime)

    return answer


for test in range(1, testCase + 1):
    n, m, k, a, b = map(int, input().split())

    # 초기화
    receptionCounterProcessingTime = list(map(int, input().split()))
    receptionCounterProcessingTime.insert(0, 0)
    maintenanceCounterProcessingTime = list(map(int, input().split()))
    maintenanceCounterProcessingTime.insert(0, 0)

    # 도착 시간
    comeInTime = collections.deque(list(map(int, input().split())))

    # 창구 및 대기줄 초기화
    receptionCounter = [0 for _ in range(n + 1)]
    maintenanceCounter = [0 for _ in range(m + 1)]
    receptionQueue = collections.deque([])
    maintenanceQueue = collections.deque([])

    # 매초마다.
    answer = 0
    k = 0
    for t in range(2300):
        k = comeInReceptionQueue(t, comeInTime, receptionQueue, k)
        proccessReceptionCounter(receptionCounter, receptionQueue, maintenanceQueue, receptionCounterProcessingTime, n)
        answer = proceessMaintenanceCounter(maintenanceCounter, maintenanceQueue, maintenanceCounterProcessingTime, m,
                                            a, b,
                                            answer)

        if not comeInTime and not findCounter(receptionCounter,n) and not findCounter(maintenanceCounter,m):
            break

    if answer == 0:
        answer = -1

    print("#{} {}".format(test, answer))

풀이시간은 2시간... 왜 이렇게 오래 걸렸고, 코드가 길어졌고, 지저분해졌는지 설명해보겠다.

오래 걸린 이유

1. class의 property 설정.

   • 자바에서 getter setter 메서드로 필드 값을 주고 변경하는 것에 신경썻던지라 여기서도 그와같이 구현했다. 그런데 eclipse에서는 손쉽게 작성할 수 있던 반면 파이참에서는 어떻게 할 지 몰라서 직접 작성했다.

2. 길어진 변수명, 그리고 python의 특성.

   • 변수명에 충분한 설명을 넣으려다보니 변수명이 길어졌다. 그런데, 함수구현시 이미 작성된 변수에 대해 자동완성 기능을 받을 수 없었다.
   • java, c같은 경우 변수에 타입을 선언함으로써 어떤 애인지 idle이 알고 객체에 있는 메서드를 추천해주는데 python은 타입을 선언하지 않다보니 직접 작성해줘야 했다.
   • 변수명 길이 + idle지원x => 오타 발생 으로 인해 수정하느라 시간이 오래걸렸다.

3. 문제 잘못이해

   • 0<=tk<=1000이라하여 1000초까지만 고려했는데 테케 37번에서 막혔다.

     잘 생각해보니

코드가 길어진 이유 + 지저분해진 이유

모듈화가 잘 안됬다.

프로세스 구현시 시간을 조금~이라도 줄이고자 남은 서비스시간이 0이 됬을 때 바로 이동시켰다.

그런데 접수 데스크의 초기값을 0으로 선언한 반면, 그 안에 들어가는 값은 객체도 있기 때문에 typesafe하지 못했다.

객체에서 남은 시간을 참조할 수 있으나, 0에선 남은 시간을 참조할 수 없기 때문.

이때문에 객체의 남은 시간이 0일 때와 숫자가 0일 때의 절차가 비슷하므로 중복된 코드가 들어갔다.

정확히 같지는 않아서 같은 코드를 붙여넣는 방식으로 코드를 작성했다.

차라리 서비스시간 1감소하는 함수,

숫자가 0인것 아닌것을 구분하여 큐로 넘기는 함수를 작성했다면, 리스트에 한가지 타입으로 통일했다면 깔끔했을 것이다.

1씩 감소하는 걸 쓰는건 접수창구, 정비창구에서도 쓰일 수 있으니 재사용도 가능했을 것이다..