[프로그래머스] Python 알고리즘 스터디 - 1주차 Queue & Heap

1주 차

Queue & Heap

---

 

< 1. 기능 개발 >

def solution(progresses, speeds):
    days = [0] * len(progresses)
    criteria, cnt = 0, 1
    ans = []
    
    for i in range(len(progresses)):
        while progresses[i] < 100:
            progresses[i] += speeds[i]
            days[i] += 1
    
    for j in range(len(days)):
        if days[j] > criteria:
            criteria = days[j]
            if j == 0: continue
            ans.append(cnt)
            cnt = 1
        else: cnt += 1
        if j == len(days)-1: ans.append(cnt)
    return ans

---

< 2. FloodFill >

전형적인 BFS 탐색 문제였다.

 

1) BFS 사용, 코드 리뷰받기 전

from collections import deque

def solution(n, m, image):
    direction = [(1,0),(-1,0),(0,1),(0,-1)]
    cnt = 0
    
    for x in range(n):
        for y in range(m):
            if image[x][y] < 0: continue
            cur_color = image[x][y]
            image[x][y] = -image[x][y]
            Q = deque([(x, y)])
            
            while Q:
                cur_x, cur_y = Q.popleft()

                # 상하좌우 탐색
                for move in direction:
                    Nx, Ny = move[0] + cur_x, move[1] + cur_y
                    if (0<=Nx<n) and (0<=Ny<m) and cur_color == image[Nx][Ny]:
                        # 방문한 지점은 다시 방문하지 않도록 음수로 값을 변경합니다.
                        image[Nx][Ny] = -image[Nx][Ny]
                        Q.append((Nx, Ny))
            cnt += 1
    return cnt

2) 피드백 수정

from collections import deque

def solution(n, m, image):
    direction = [(1, 0),(-1, 0),(0, 1),(0, -1)]
    cnt = 0
    
    for x in range(n):
        for y in range(m):
            if image[x][y] < 0: continue
            cur_color = image[x][y]
            image[x][y] = -image[x][y]
            Q = deque([(x, y)])
            
            while Q:
                cur_x, cur_y = Q.popleft()

                # 상하좌우 탐색
                for move in direction:
                    Nx, Ny = move[0] + cur_x, move[1] + cur_y
                    if (0 <= Nx < n) and (0 <= Ny < m) and cur_color == image[Nx][Ny]:
                        # 방문한 지점은 다시 방문하지 않도록 음수로 값을 변경합니다.
                        image[Nx][Ny] = -image[Nx][Ny]
                        Q.append((Nx, Ny))
            cnt += 1
    return cnt

 

(1,0)이라던가 0 <=Nx <n 이런 부분을 띄어 써줘야 한다는 피드백을 받아서 수정했다.

사소하지만 코드 짤 때 스타일에 맞게 짜는 것도 중요하다는 걸 기억하자.

 

하나만 풀기는 아쉬워서 leetcode에서 관련 문제를 더 풀었다.

200. Number of Islands

994. Rotting Oranges

 

---

< 3. 더 맵게 >

1. 내 코드

import heapq

def solution(scoville, K):
    # 계속해서 최소값을 찾아 계산하는 문제이므로 min heap을 사용합니다.
    heapq.heapify(scoville)
    cnt = 0
    
    while scoville[0] < K:
        # scoville를 계산하기 위해서는 길이가 최소 2개여야합니다.
        # (연산에서 제일 작은 값과 그 다음 작은 값이 필요하므로)
        if len(scoville) >= 2:
            first_lowest = heapq.heappop(scoville)
            second_lowest = heapq.heappop(scoville)
            heapq.heappush(scoville, first_lowest + second_lowest * 2)
            cnt += 1
        else: return -1
    return cnt

 

 

2. try-except 문 사용한 코드

 

def solution_2(scoville, K):
    # 계속해서 최소값을 찾아 계산하는 문제이므로 min heap을 사용합니다.
    heapq.heapify(scoville)
    cnt = 0
    
    while scoville[0] < K:
        # scoville를 계산하기 위해서는 길이가 최소 2개여야합니다.
        # (연산에서 제일 작은 값과 그 다음 작은 값이 필요하므로)
        # 길이가 1이라면 오류가 나므로 -1값을 리턴해서 종료됩니다.
        try : 
            first_lowest = heapq.heappop(scoville)
            second_lowest = heapq.heappop(scoville)
            heapq.heappush(scoville, first_lowest + second_lowest * 2)
            cnt += 1
        except:
            return -1
    return cnt

전체적으로 코드는 같지만 try-except문을 사용해서도 풀어봤다.

특히나 stack 문제를 풀 때는 유용하게 쓰이는 것 같다.

 

'더 맵게 문제'는 전에도 풀어봤는데, 그때는 안 풀려서 오랫동안 잡고 있었던 기억이 난다.

이번에 풀 때는 문제 자체와 코드는 생각이 나지 않았는데도 알고리즘 공부를 열심히 해서 그런지 쉽게 풀려서 뿌듯했다.

 

---

< 4. 배상 비용 최소화 >

배상 비용 최소화 문제는 문제 설명은 어려운데, 큰 숫자를 제거해주면 풀리는 간단한 문제다.

 

1. 내 코드

# Keypoint : 우선순위 큐 사용
# 시간 복잡도 : O(N)
import heapq

def solution(Number, works):
    if sum(works) <= Number: return 0
    heap_works = []
    
    for work in works:
        heapq.heappush(heap_works, -work)
        
    for _ in range(Number):
        biggest_work = heapq.heappop(heap_works) + 1
        heapq.heappush(heap_works, biggest_work)
        
    ans = sum([n ** 2 for n in heap_works])
    return ans

# heapq의 heapify 연산은 시간 복잡도 : O(N)

 

2. 코드 피드백 수정

import heapq

def solution(Number, works):
    if sum(works) <= Number: return 0
    heap_works = []
    
    for work in works:
        heapq.heappush(heap_works, -work)
        
    for _ in range(Number):
        heapq.heapreplace(heap_works, heap_works[0] + 1)
        
    ans = sum([n ** 2 for n in heap_works])
    return ans

heap에서 push와 pop이 동시에 일어나는 경우네는 replace로 한 번에 대체할 수 있다는 피드백을 들었다.

 

우선순위 큐를 사용해서 Python에서는 min-heap이 기본이기 때문에 음수로 변환하면 max-heap으로 사용할 수 있다.

제일 큰  heapify 연산은 heap에 있는 모든 노드를 확인하기 때문에 시간 복잡도는 O(N)이다.

---

< 5. 게임 아이템 >

1. 첫 번째 코드

import heapq

def solution(healths, items):
    healths = sorted(healths)
    item_queue = []
    for idx, val in enumerate(items):
        # 체력 / 공격력 순이 되게 바꿔줌
        item_queue.append((val[0], val[1], idx+1))
    heapq.heapify(item_queue)
    
    ans, candidate = [], []
    DOWN_HP, POWER, INDEX = 0, 1, 2
    for health in healths:
        while item_queue and (health - item_queue[0][DOWN_HP] >= 100):
            cur_item = heapq.heappop(item_queue)
            heapq.heappush(candidate, (-cur_item[POWER], cur_item[INDEX]))
        if candidate:
            biggest_power = heapq.heappop(candidate)
            ans.append(biggest_power[1])
    return sorted(ans)

 

2. 코드 개선

import heapq

def solution(healths, items):
    healths = sorted(healths)
    item_queue = [(item[1], item[0], idx) for idx, item in enumerate(items, 1)]
    heapq.heapify(item_queue)
    
    ans, candidate = [], []
    DOWN_HP, POWER, INDEX = 0, 1, 2
    for health in healths:
        while item_queue and (health - item_queue[0][DOWN_HP] >= 100):
            cur_item = heapq.heappop(item_queue)
            heapq.heappush(candidate, (-cur_item[POWER], cur_item[INDEX]))
        if candidate:
            biggest_power = heapq.heappop(candidate)
            ans.append(biggest_power[1])
    return sorted(ans)

같은 코드이지만 item_queue를 좀 더 보기 좋게 고쳐줬다.

 

 

 

* PriorityQueue 모듈을 사용할 수도 있지만 PriorityQueue 모듈은 heapq 모듈에 비해 속도가 느리다.

 

---

후기

1주 차에는 Queue와 Heap 알고리즘 문제를 풀어봤다.

Queue의 대표적인 알고리즘인 BFS 문제도 다루고, min-heap, max-heap 문제도 풀면서 heap 사용하면서 heap모듈 사용에도 익숙해졌다.

 

문제 풀기 바빠서 띄어쓰기라던가 변수 이름 규칙은 신경 쓰지 않고 코드를 짜곤 하는데, 협업에서 한다면 큰일 날 일이다 ㅋㅋ

Python 같은 경우는 PEP8 스타일 가이드를 따른다고 하니까 가끔 봐 둬야겠다.

 

Python PEP8 style guide Cheat Sheet