[Python] 백준 1655 가운데를 말해요

문제 링크 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

1. 접근 방법

입력을 계속 받으며 중간 값을 출력해야 한다. 이때, 입력이 많기 때문에 계속 정렬을 한다거나 탐색을 하면 시간 초과가 날 것으로 보인다.

그렇기 때문에 중간값을 기준으로 큰 값, 작은 값을 각각 보관하고, 입출력이 많을 수 있기 때문에 heap 구조를 활용했다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1600/1655.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

처음 입력값은 중간 값으로, 그다음부터 입력값은 규칙에 따라 실행한다. 다음과 같은 순서로 진행한다.

위에서 mid에 배정된 값은 중간값, 왼쪽 오른쪽 부분은 각각 중간값보다 작은 값과 큰 값들이다. 이 그림에서는 선형적으로 기록했지만, 실제로는 heap구조에 기록된다.

우선 입력을 받으면 mid값보다 큰지 작은지 확인한 후 각 조건에 맞는 heap에 저장한다. 그리고 mid값이 중간값 조건, 만약 중간값이 2개(총개수가 짝수개)라면 더 작은 값을 출력하기 위해 큰 숫자를 보관하는 heap 크기가 작은 값을 보관하는 heap과 크기가 같거나 1개 더 저장하는 방식을 선택했다.

(아래 코드 설명 부분에서는 각 변수 small_val, large_val로 작성하겠다.)

 

if i % 2:
    if k < mid:
        heappush(large_val, mid)
        mid = -heappushpop(small_val, -k)
    else:
        heappush(large_val, k)
else:
    if k > mid:
        heappush(small_val, -mid)
        mid = heappushpop(large_val, k)
    else:
        heappush(small_val, -k)

코드로는 다음과 같이 구현된다.

우선 i가 홀수, 짝수인지에 따라 구분되는데, 이는 전체 숫자 갯수가 짝수, 홀수가 될 때를 의미한다.

만약 3번째 값인 2가 입력될 때를 생각해보자, 그렇다면 small_val에는 개 값이, large_val에는 2개 값이 저장되게 되는데,  그렇게 되면 mid값이 중간값이 될 수 없다. 그래서 지금 mid 값을 small_val에 추가, 새로운 입력을 large_val에 넣으면서 large_val의 최솟값을 mid값으로 지정한다. (첫 if-else 구분에서 else, 다음 if조건에 성립하는 경우)

다음으로 4번째 값인 10이 들어올때는 small_val, large_val 모두 1개 값을 가지고, mid값보다 더 큰 값이 입력되므로 large_val에 추가한다. (첫 if문을 만족, 두 번째 if문을 만족하지 않는 경우)

 

---

3. 생각 정리

heap구조는 최대, 최소값을 구하고 활용할 때 많이 사용했지만, 이번 문제처럼 여러 개의 heap구조를 상황에 나누어 활용하는 문제는 많이 접해보지 않아 처음 접근할 때 많은 고민을 했다. 그리고 python-heapq는 최소 heap으로만 동작하여 small_val에는 -1을 곱한 값으로 넣는 등의 동작도 고려해야 했다.