[백준] 1665번: 가운데를 말해요 - Python

dev-jjun·2023년 8월 28일

코딩테스트 준비

목록 보기

11/11

오랜만에! 알고리즘 문제 풀이를 업로드해보려 한다. 확실히 그냥 문제를 주석달며 푸는 것과 블로그에 글을 작성하며 푸는 것은 차이가 있다. 문제를 어떻게 하면 쉽게 이해하고 풀이를 효율적으로 공유할 수 있을지 더 고민하게 되기 때문인 것 같다.

갑자기 급하게 파이썬으로 코딩테스트를 볼 일이 생겨서 파이썬 문법도 상기시킬 겸 본격적인 알고리즘 공부 시작 전에 백준 문제풀이를 조금씩 실천해보려 한다!

GOGOGOGO 🏃🏻‍♀️💨

🔗 문제

BOJ 1655 : 가운데를 말해요

난이도 - 골드 2

알고리즘 분류 - 자료구조, 우선순위 큐

💬 풀이

단순하게 접근했던 나의 풀이..

T = int(input())

def mid_num(nums):
    nums.sort()
    # len: 3 -> 1 = 3 // 2 4 ->1
    if len(nums) % 2 == 0:
        idx = len(nums) // 2 - 1
    else:
        idx = len(nums) // 2
    return nums[idx]
nums = []
result = []
for i in range(T):
    nums.append(int(input()))
    result.append(mid_num(nums))

for i in range(T):
    print(result[i])

파이썬 리스트 등의 문법을 정말 활용 못하는 티가 나는 코드이다. 말 그대로 리스트 정렬 후, 중간 인덱스 값을 가져오는 문제인데 대충 몇 개 수로 이루어진 리스트에서 인덱스가 짝수/홀수일 때에 따라 어떤 계산이 필요한지 유추해보고 if-else 조건식으로 구현한 것이다.

'우선순위 큐'를 이용하라!

우선순위 큐를 구현할 때 주로 힙 자료구조를 사용할 수 있다.
힙이란, 힙 순서 속성을 만족하는 완전 이진 트리이다!

힙 순서 속성은 뭔데? [기본 Rule]

부모 노드가 자식 노드보다 작거나 같은 순서 규칙만 지키면 OK

우선순위 큐로 구현할 때 사용 → 어떻게 넣든 삽입 순서에 상관없이, 우선순위대로 출력

즉, 작은 순서로 데이터 출력이 가능 (Min Heap)

cf. 데이터가 큰 순서로 출력하려면? 최대힙(Max Heap) (자식이 부모보다 항상 큰 값을 가지는 규칙)

*최소 힙을 최대 힙처럼 사용하려면? 단순히 숫자에 -1을 곱해서 사용하면 된다.

힙을 주로 어디에 쓰는가?

우선순위 큐(Priority Queue)
들어온 순서와 상관없이 우선 순위가 높은 데이터가 먼저 나오는 구조

*보통 더 높은 우선순위를 더 낮은 값으로 표현

in Python...

heapq를 사용 *이게 조금 더 저수준 (우선순위 큐가 힙을 기반으로 만들어진 자료구조이므로) 출력 순서는 트리로 그려서 표현하고 순회하는 것으로 해석하면 된다!
- heapq.heapify(heap) 트리 순서 규칙에 따라 힙 트리를 만든다.
- 작은 순서대로 출력하려면? heapq.heappop(heap)[1])
PriorityQueue를 사용

우선순위 큐를 이용한 것과 단순 구현을 비교해보자!

우선순위 큐의 특성에 따르면, 삽입 순서와는 무관하게 새로운 값을 추가할 때마다 정렬이 유지되어야 한다. 이때 최소 힙과 최대 힙은 각각 오름차순 정렬, 내림차순 정렬에 대응된다고 볼 수 있다.
(즉 위 코드에서 for문을 돌며 매번 sort()로 정렬한 부분을 우선순위 큐 자료구조로 더 간단하게 구현할 수 있는 것이다.)

힙 트리를 사용함으로써 조회 속도를 빠르게 하려면 루트에 있는 원소를 꺼낼수록 유리하다. 접근할 트리의 깊이가 얕을수록 성능이 좋아지는 것이다.

따라서, 중간값을 가져와야 하는 본 문제에서는 최소 힙과 최대 힙을 모두 사용하여 중간값이 루트에 있도록 임의대로 정렬한 후에 결과를 출력하고자 한다.

💡 정렬 전략

홀수와 짝수로 구분

짝수는 최대 힙에, 홀수는 최소 힙에 일단 push를 한 뒤에 루트끼리 비교했을 때 최대 힙의 루트원소가(-max_heap[0]) 더 작으면 힙의 루트원소를 서로 교체해준다.

힙을 파이썬 배열로 구현하므로, 최대 힙의 특성에 부합하게 음수로 저장하고 최소 힙은 양수로 저장한다.

최대힙의 루트원소=최댓값, 최소힙의 루트원소=최솟값
*높은 우선순위를 주고 싶은 것에 음수값 return

💻 코드

import heapq

n = int(input())

max_heap = []
min_heap = []

for i in range(n):
    x = int(input())
    if i % 2 == 0:
        heapq.heappush(max_heap, -x)
    else:
        heapq.heappush(min_heap, x)

    if max_heap and min_heap and -max_heap[0] > min_heap[0]:
        maxnum = -heapq.heappop(max_heap)
        minnum = heapq.heappop(min_heap)

        heapq.heappush(max_heap, -minnum) 
        heapq.heappush(min_heap, maxnum)

    print(-max_heap[0])

📊 정리

📍 오늘의 메모

정말 오랜만에 제대로 난이도 높은 문제 풀려고 하다보니 문제접근을 어떻게 하는지 완전히 잊었나보다!
단순하게 문제 그대로 해석하여 코드에 옮기는 '억지기법' 식의 풀이도 좋지만, 대부분 통과를 못할 가능성이 크다. 이럴때는 알고리즘 분류에서 힌트 얻기
Python에서 시간초과 발생 시 TIP!
```
``` python
import sys

input = sys.stdin.readline
n = int(input())
```
```
입력받을 때 그냥 input() 대신 sys.stdin.readline()을 사용하자!

➔ sys.stdin.readline()이 더 빠른 이유

input()에서는 다음과 같은 중간과정을 거치기에 속도가 비교적 느리다.
1. 매개변수로 문자열이 들어오면 프롬프트 메시지로 출력
2. 입력받은 값의 개행 문자를 삭제시키고 반환