[1주차 큐, 힙] 코드 리뷰

1. 1. 큐 Lv 2 - 최대 용량이 정해진 FIFO 큐 클래스

      

      

      

    
    

      <python />
    
class MyStack(object):
    def __init__(self):
        self.lst = list()

    def push(self, x):
        self.lst.append(x)

    def pop(self):
        return self.lst.pop()

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


class MyQueue(object):
    def __init__(self, max_size):
        self.stack1 = MyStack()
        self.stack2 = MyStack()
        self.max_size = max_size

    def qsize(self):
        return self.stack1.size() + self.stack2.size()

    def push(self, item):
        if self.qsize() == self.max_size:
            return False
        else:
            self.stack1.push(item)
            return True

    def pop(self):
        try:
            if self.stack2.size() == 0:
                while self.stack1.size() > 0:
                    self.stack2.push(self.stack1.pop())
            result = self.stack2.pop()
        except IndexError:
            return False
        return result


n, max_size = map(int, input().strip().split(' '))
my_queue = MyQueue(max_size)

for _ in range(n):
    command = input().split()
    if "PUSH" in command:
        print(my_queue.push(int(command[1])))
    elif command[0] == "POP":
        print(my_queue.pop())
    elif command[0] == "SIZE":
        print(my_queue.qsize())

• MyQueue 클래스 내에 MyStack을 받는 인스턴스가 두개 주어졌으므로, 한쪽에서 다른쪽으로 원소를 옮기는 방식으로 수행해야함.
• 예외처리를 "if self.size() == 0" 과 같이 조건을 걸어서 별도로 처리하는 방법을 추천.

 

 

2. 2. 큐 Lv 2 - 기능개발

      

      

      

    
    

      <python />
    
from collections import deque
from math import ceil

def solution(progresses, speeds):
    new_list = deque()

    for i in range(len(progresses)):
        new_list.append(ceil((100 - progresses[i]) / speeds[i]))

    cnt = 1
    max_value = new_list[0]
    result = []

    for i in range(1, len(new_list)):
        if max_value >= new_list[i]:
            cnt += 1
        else:
            result.append(cnt)
            cnt = 1
            max_value = new_list[i]
    result.append(cnt)

    return result

• 리스트 이름은 구체적으로 명시하여 무엇을 의미하는지 알아볼 수 있도록 하자. 예를 들면 finished_dates(기능 개발이 끝난 날짜를 담으므로), days_left(개발이 끝날때까지 남은 일 수), due_date(개발이 완료되어야하는 날짜) 등등.
• 특정 인덱스 값을 변경해야하는 상황 등이 아니면 가급적 인덱스를 사용하기보다는 for value in values 와 같이 사용하는 걸 권장.인덱스를 쓰면 에러가 날 가능성이 높아짐.ㅠ

      

      

      

    
    

      <python />
    
cnt = 0
max_value = new_list[0]
result = []

for finished_date in new_list:

 

 

3. 3. 힙 Lv 2 - 더 맵게

      

      

      

    
    

      <python />
    
import heapq

def solution(scoville, K):
    cnt = 0
    heapq.heapify(scoville)

    for _ in range(len(scoville)):
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        new = first + second * 2
        heapq.heappush(scoville, new)
        cnt += 1

        if scoville[0] >= K:
            return cnt
            break

    if scoville[0] < K:
        return -1

• line 16 : return아래에 break가 있는 경우, break가 수행되지 않으므로 지워도 됨.
• 시간 복잡도 구하기 : N = len(scoville)일 때

1. 5번째 줄의 heapify는 O(NlogN)만큼 소요
2. for문의 시간복잡도는 O(NlogN)
   • for문은 N번 실행되고
   • for문 앞의 heappop과 heappush의 시간복잡도는 O(logN) 
   • 따라서 O(logN)이 N번 실행되므로 for문의 시간복잡도는 O(NlogN)

   >> 1과 2를 종합적으로 보면 전체 시간복잡도는 O(NlogN)

 

 

4. 4. 힙 Lv 2 - 배상 비용 최소화

      

      

      

    
    

      <python />
    
import heapq

def solution(no, works):
    cnt = 0
    works = [(-ele, ele) for ele in works]
    heapq.heapify(works)

    while cnt < no:
        max_num = heapq.heappop(works)[1]
        if max_num == 0:
            return 0
            break
        else:
            max_num -= 1
            heapq.heappush(works, (-max_num, max_num))
            cnt += 1

    return sum([i[1] ** 2 for i in works])

• 임의의 음수 값을 제곱하면 양수가 되기 때문에 line.5에서 (-ele, ele) 튜플로 만들으신 것을 -ele로 변경해서 풀이해보시면 좋을 듯!