[알고리즘 문제 풀이🙄] 피자 굽기

📌 문제 요약

화덕에 들어갈 수 있는 피자의 수는 N개이다. 총 M개의 피자가 주어질 때, 각 피자의 치즈가 모두 녹는 데 걸리는 시간은 모두 다르다. 화덕 내부의 피자 받침이 천천히 회전하므로 1번에서 피자를 잠시 꺼내 치즈의 녹은 정도를 확인하고 다시 같은 자리에 입력할 수 있으며, 치즈가 모두 녹은 피자는 빼낸 후 새로운 피자를 같은 자리에 입력할 수 있다.

 

😖 내가 생각한 로직

 

1. M개의 피자에 대해 각각의 피자 치즈가 모두 녹는 데 걸리는 시간을 list로 받는다.

2. 리스트의 요소들을 enumerate()를 활용하여 [인덱스, value]로 값을 수정한다.

3. 리스트를 역순으로 정렬한다.

4. 화덕에 들어가 있는 피자의 수가 0이 될 때까지 아래의 반복문을 실행한다.

    4-1. 각 피자의 남은 치즈 양을 1/2로 감소시킨다.

    4-2. 피자를 하나씩 꺼내어 확인한다. (deQueue())

    4-3. 만약 피자의 치즈가 다 녹았으면 대기중인 피자를 해당 자리에 넣고, 녹지 않았으면 해당 자리에 다시 피자를 넣음

           ( → 여기서 문제 생겼음!!!! 바보같이 enqueue()로 다시 넣어줘버려서 자꾸 순서가 꼬였었다.😰)

5. 4번 과정을 반복하여 최종 출력되는 피자의 인덱스값을 산출한다.

 

🤗 제출 후 pass한 코드

def enQueue(item):
    global rounded_queue
    global rear
    global out

    if isFull():
        print("Queue is Full now!")
    else:
        rear = (rear + 1) % N
        rounded_queue[rear] = item


def deQueue():
    global rounded_queue
    global front
    global rear

    if isEmpty():
        print("Queue is Empty now!")
    else:     
        front = (front + 1) % N
        return rounded_queue[front]


def isFull():
    global rounded_queue
    global rear

    return (rear + 1) % N == front


def isEmpty():
    return front == rear
    

T = int(input())

for tc in range(1, T + 1):
    # N: 화덕의 크기, M: 피자의 개수
    N, M = map(int, input().split())
    lst = list(map(int, input().split()))
    
    prev = M - N - 1
    out = 0

    for (i, l) in enumerate(lst):
        lst[i] = [i, l]
    
    lst.reverse()

    rounded_queue = [None] * N
    front = -1
    rear = -1
    ctn = True

    for n in range(N):
        enQueue(lst.pop())

    for m in range(M):
        front = -1
        rear = N - 1
        for n in range(N):
            if rounded_queue[n] != None:
                rounded_queue[n][1] //= 2

        for n in range(N):
            temp = deQueue()
            rounded_queue[front] = None

            if temp == None:
                continue
			
            # 만약 치즈가 다 녹으면
            if temp[1] == 0 :  
            	# 빼낸 개수 + 1
                out += 1      
                # 만약 아직 대기중인 피자가 있다면
                if prev >= 0:             
                	# 집어넣을 피자를 그것으로 설정
                    temp = lst[prev]                
                    prev -= 1  
                # 빼낸 개수가 총 피자 개수와 같다면
                elif out == M:                      
                    # 마지막 피자 번호
                    print(f'#{tc} {temp[0] + 1}')
                    ctn = False                     # 최종 탈출
                # 만약 대기중인 피자가 없고, 빼낸 개수가 총 개수와 같지 않다면
                else:
                    continue
            
            rounded_queue[front] = temp 

        if ctn == False:
            break

 

🧐 참고해 볼 만한 코드

# 가장 마지막까지 남아있는 피자 번호
T = int(input())
for tc in range(1, T + 1):
    # N : 화덕 크기, M : 피자 개수
    N, M = map(int, input().split())
    arr = list(map(int, input().split()))

    temp = [0] * (M + 1)
    for i in range(M):
        temp[i + 1] = arr[i]

    pizza = []
    for idx, c in enumerate(temp):  # idx : 피자번호, c : 치즈양
        pizza.append([idx, c])  # [[0, 0], [1, 7], [2, 2], [3, 6], [4, 5], [5, 3]]
    pizza = pizza[1:]  # [[1, 7], [2, 2], [3, 6], [4, 5], [5, 3]]

    # 빈 화덕에 피자 넣기
    bake = []
    for _ in range(N):
        p = pizza.pop(0)
        bake.append(p)

    # print(bake)     # [[1, 7], [2, 2], [3, 6]] >> 화덕에 있는 피자
    # print(pizza)    # [[4, 5], [5, 3]] >> 대기중인 피자

    # 피자개수 1개 남을때 까지 반복
    while len(bake) > 1:
        p = bake.pop(0)  # 피자 꺼내서
        c = p[1] // 2  # 피자 치즈 양 확인

        if c != 0:  # 0이 아니면
            p[1] = c
            bake.append(p)  # 다시 넣기

        else:  # 0이고
            if pizza:  # 굽히지 않은 피자가 있다면
                new_p = pizza.pop(0)  # 새로운 피자 넣기
                bake.append(new_p)

    print(f'#{tc} {bake[0][0]}')

→ 짝꿍의 코드!

 

😫 내가 구현한 코드의 문제점

 

이 글의 '내가 생각한 로직' 파트를 작성하면서 내 코드의 문제점이 무엇이었는지를 깨달았다. 원형 큐 자료구조를 사용해야 한다는 생각 매몰되어 바보같이 큐에 데이터를 입력하는 것은 무조건 enQueue() 메서드를 사용해야 한다고만 생각했다. 차근차근 글로 작성하며 생각해보니, 내가 바보같이 피자를 꺼낸 자리가 아닌 queue의 rear 자리에 계속 값을 넣고 있었다는 것을 한번에 알아차릴 수 있었다.

 

 

😎 앞으로의 개선 방향

알고리즘 문제를 풀 땐 항상 내 로직을 글로 먼저 작성해봐야겠다는 생각을 했다. 태블릿에 동작 과정을 그림으로 그리는 것도 좋지만, 글로 명확하게 적어두면 확실히 덜 헷갈리고 디버깅하는 데 도움이 많이 되는 것 같다. 계속계속 화이팅해야지!