자료구조 문제풀이 - 주문처리 (큐)

 

class Queue:
    def __init__(self) :
        self.myQueue=[]

    def push(self, n) :
        self.myQueue.append(n)

    def pop(self) :
        if self.empty()==1:
            return
        else:
            del self.myQueue[0]


    def size(self) :
        return len(self.myQueue)

    def empty(self) :
        if self.size()==0:
            return 1
        else:
            return 0

    def front(self) :
        if self.empty()==1:
            return -1
        else:
            return self.myQueue[0]


    def back(self) :

        if self.empty()==1:
            return -1
        else:
            return self.myQueue[-1]

'''
함수 processOrder를 구현하세요.
'''

class orderInfo:
    '''
    이 부분은 수정하지 마세요.
    '''
    def __init__(self, t, d, v):
        self.time = t
        self.duration = d
        self.vip = v

def processOrder(orders) :
    '''
    주문 정보가 주어질 때, 주문이 처리되는 순서를 반환합니다.
    '''
    result = []
    normalQueue = Queue()
    vipQueue=Queue()

    jobEndTime=0 

    for i in range(len(orders)):

        if orders[i].vip==0: #일반 고객의 경우
            normalQueue.push(i) 
        else: #vip 고객인 경우
            vipQueue.push(i)
           
           
    while not(normalQueue.empty()==1 and vipQueue.empty()==1): #주문이 있다면 계속 반복
            #normal or vip
        targetQueue = selectQueue(normalQueue, vipQueue, jobEndTime, orders)
            
        index=targetQueue.front()	 #처리해야할 주문 번호를 가져오기
            
         #주문을 처리한다. ==> jobEndTime을 증가시킨다.
         #jobEndTime > orders[Index].time 인 경우 => 주문 밀린 상태 => 바로 다음 작업 시작
            
         #jobEndTime < order[Index].time 인 경우 => 주문 밀려있지 않음
         #=> 다음 작업이 들어온 시점에 처리(여유가 있음)
        jobEndTime = max(jobEndTime, orders[index].time) + orders[index].duration
            
        result.append(index+1)
        targetQueue.pop()
            
    return result


def selectQueue(normalQueue, vipQueue, time, orders):
        normalIndex=normalQueue.front()
        vipIndex=vipQueue.front()

        if vipIndex == -1:
            return normalQueue
        
        if normalIndex==-1:
            return vipQueue
        
        #밀린 작업이 노말에도 없고 vip에도 없는 경우
        #더 빨리 도착한 주문을 처리한다.
        if time < orders[normalIndex].time and time < orders[vipIndex].time:
            if orders[vipIndex].time<=orders[normalIndex].time:
                return vipQueue
            else:
                return normalQueue

        #밀린 작업이 노말에만 있는 경우
        if time>=orders[normalIndex].time and time < orders[vipIndex].time:
            return normalQueue
        
        #밀린 작업이 vip에만 있는 경우
        if time>=orders[vipIndex].time and time < orders[normalIndex].time:
            return vipQueue

        #밀린 작업이 노말에도 있고 vip에도 있는 경우
        return vipQueue

 

 

queue 라이브러리를 사용해서 푼 경우

empty=> 0과 1이 아닌 True/ False 반환

front/ back 존재 안함

push => put

pop=> get

'''
함수 processOrder를 구현하세요.
'''
    
from queue import Queue

class orderInfo:
    '''
    이 부분은 수정하지 마세요.
    '''
    def __init__(self, t, d, v):
        self.time = t
        self.duration = d
        self.vip = v

def processOrder(orders) :
    '''
    주문 정보가 주어질 때, 주문이 처리되는 순서를 반환합니다.
    '''
    jobEndTime=0

    result = []

    normalQueue = Queue()
    vipQueue=Queue()

    jobEndTime=0 
    curTime=-1

    for i in range(len(orders)):
        curTime=orders[i].time

        if orders[i].vip==0: #일반 고객의 경우
            normalQueue.put(i) 
        else: #vip 고객인 경우
            vipQueue.put(i)
        
    while not(normalQueue.empty() and vipQueue.empty()):
            #normal or vip
        targetQueue = selectQueue(normalQueue, vipQueue, jobEndTime, orders)
            
        #처리해야할 주문 번호를 가져오기
        index=targetQueue.queue[0]
            
        #주문을 처리한다. ==> jobEndTime을 증가시킨다.
        #jobEndTime > orders[Index].time 인 경우 => 주문 밀린 상태 => 바로 다음 작업 시작
            
        #jobEndTime < order[Index].time 인 경우 => 주문 밀려있지 않음
        #=> 다음 작업이 들어온 시점에 처리(여유가 있음)
        jobEndTime = max(jobEndTime, orders[index].time) + orders[index].duration
        result.append(index+1)
        targetQueue.get()
            
    return result

def selectQueue(normalQueue, vipQueue, time, orders):
        normalIndex=-1 if len(normalQueue.queue) ==0 else normalQueue.queue[0]
        vipIndex=-1 if len(vipQueue.queue) ==0 else vipQueue.queue[0]

        if vipIndex == -1:
            return normalQueue
        
        if normalIndex==-1:
            return vipQueue
        
        #밀린 작업이 노말에도 없고 vip에도 없는 경우
        #더 빨리 도착한 주문을 처리한다.
        if time < orders[normalIndex].time and time < orders[vipIndex].time:
            if orders[vipIndex].time<=orders[normalIndex].time:
                return vipQueue
            else:
                return normalQueue

        #밀린 작업이 노말에만 있는 경우
        if time>=orders[normalIndex].time and time < orders[vipIndex].time:
            return normalQueue
        
        #밀린 작업이 vip에만 있는 경우
        if time>=orders[vipIndex].time and time < orders[normalIndex].time:
            return vipQueue

        #밀린 작업이 노말에도 있고 vip에도 있는 경우
        return vipQueue