• TOC {:toc}

이 글은 백준 온라인 저지의 2696번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.02

메모리 시간 코드 길이
31356 KB 80 ms 826 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 13:27:37 13:28:07
풀이 생각 13:28:08 13:31:10
코딩 13:32:18 13:48:33
디버깅 13:48:34 14:16:13 
import sys
from heapq import heappush, heappop
input = lambda: sys.stdin.readline().rstrip()

UNIT = 10
for _ in range(int(input())):
    M = int(input())
    N = (M + 1) // 2
    print(N)

    S = []
    L = []
    res = []

    for _ in range(M // UNIT + 1):
        for i, x in enumerate(map(int, input().split())):
            if (i + 1) % 2:
                if not L or x < L[0]:
                    heappush(S, -x)
                else:
                    heappush(L, x)
                    heappush(S, -heappop(L))
                res.append(-S[0])
            else:
                if x > -S[0]:
                    heappush(L, x)
                else:
                    heappush(S, -x)
                    heappush(L, -heappop(S))

    for i in range(N // UNIT + 1):
        print(*res[i * UNIT : (i + 1) * UNIT])

아이디어 & 풀이

중앙값을 구하는 방법은 [[boj-1655]]{백준 1655번} 문제의 참고 답안을 참고한다.

디버그

  • S, L을 각 케이스 반복문 밖에 써놨더니 케이스마다 S와 L이 초기화가 안 돼서 중간값이 잘못 출력됐다.
    • S, L, res 모두 케이스 반복 안으로 이동했다.
  • 입력과 출력 모두 10개 단위로 해야 하고 출력은 입력 2개당 한 개씩 출력해야 하기 때문에 입력과 출력을 각각 해야 했다.

참고 답안 1

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

for _ in range(int(input())):
    num = int(input())

    I = []
    # 여러 줄에 걸친 입력을 전부 받아온다.
    for _ in range(num // 10 + 1):
        I.extend(list(map(int, input().split())))

    S = []
    L = []
    res = []

    for i in range(len(I)):
        if len(S) == len(L):
            heappush(S, -I[j])
        else:
            heappush(L, I[j])
        # 인덱스가 짝수 일 때만 (홀수 번째 입력 일 때만)
        if i % 2 == 0:
            # S와 L root의 대소가 잘못됐으면
            if S and L and -S[0] > L[0]:
                # 두 값의 자리를 바꾼 뒤
                heappush(S, -heappop(L))
                heappush(L, -heappop(S))
            # res에 S의 root(중간값)을 추가한다.
            res.append(-S[0])

    # 중앙값의 개수를 출력한 뒤
    print(len(res))
    # res의 원소를 한 줄에 10개씩 끊어 출력한다.
    for i in range(len(res)):
        if i % 10 == 0 and i >= 10:
            print()
        print(res[i], end=" ")
    print()

아이디어 & 풀이

여러 줄에 걸쳐 있는 입력을 매 줄 받아오지 않고 입력 ‘전부’를 받아온 뒤 각 원소를 순회한다.

  • extend를 이용한다.

중앙값(홀수 번째 입력)의 개수는 res를 먼저 구성한 뒤 len(res)를 이용해 출력한다.

참고 답안 2

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

for T in range(int(input())):
    M = int(input())
    print((M + 1) // 2)

    S, L = [], []
    m = 0

    # 입력받은 각 줄의 iterator로 이루어진 2차원 리스트
    I = [map(int, input().split()) for _ in range(M // 10 + 1)]

    # "elem" for it in I    : I 안의 it(erator)에서
    #        for elem in it : it(erator) 안의 elem인 "elem"
    I = [elem for it in I for elem in it]

    for i, x in numerate(I):
        if i == 0:
            m = x
        elif x < m:
            heappush(S, -x)
            if len(S) > len(L) + 1:
                heappush(L, m)
                m = -heappop(S)
        else:
            heappush(L, x)
            if len(S) < len(L):
                heappush(S, -m)
                m = heappop(L)

        if i % 2:
            print(m, end="\n" if i % 20 == 19 else " ")
    print()

아이디어 & 풀이

입력을 이차원 리스트로 받아온 뒤 list comprehension을 이용해 일차원으로 만들어도 된다.

res를 구성하는 대신 I를 순회하면서 바로 중간값을 출력한다.

  • print()의 end에 조건문을 사용해 20번째 입력마다 (i.e., i % 20 == 19) 공백 대신 \n을 출력한다.

참고 답안 3

# 풀이 3-1
import sys
from bisect import insort
input = sys.stdin.readline

for _ in range(int(input())):
    M = int(input())
    print((M + 1) // 2)

    I = []
    for _ in range(M // 10 + 1):
        I.extend(list(map(int, input().split())))

    S = []
    res = []

    for i in range(M):
        # I의 각 원소를 S에 정렬하면서 집어넣는다.
        insort(S, I[i])
        # i가 짝수일 때 (홀수 번째 입력일 때)
        if i % 2 == 0:
            # res에 현재 S의 중간값(S[i // 2])을 추가한다.
            res.append(S[i // 2])

    # 구성한 res에 대해서
    for i in range(len(res)):
        # 각 원소의 end 옵션을 공백으로 바꿔 출력하다가
        # 10번째 원소 뒤에는 줄 바꿈을 해준다.
        print(res[i], end="\n" if i % 10 == 9 else " ") 

# 풀이 3-2
import sys
from bisect import insort
input = sys.stdin.readline

for _ in range(int(input())):
    M = int(input())
    print((M + 1) // 2)

    S = []
    for line in range(M // 10 + 1):
        # 입력받은 한 줄의 각 값에 대해
        for i, x in enumerate(map(int, input().split())):
            # S에 각 원소를 정렬하면서 집어넣는다.
            insort(S, x)
            # i가 짝수일 때 (홀수 번째 입력일 때)
            if i % 2 == 0:
                # end 옵션을 공백으로 바꿔 S의 중간값을 출력한다.
                print(S[len(S) // 2], end=" ")
        # 홀수 번째 줄일 때 줄 바꿈 한다.
        if line % 2 == 1:
            print()
    # 짝수 번째 줄일 때 줄 바꿈 한다.
    if line % 2 == 0:
        print()

# 풀이 3-3
import sys
from bisect import insort_left
input = sys.stdin.readline

for _ in range(int(input())):
    M = int(input())
    print((M + 1) // 2)

    I = []
    for _ in range(M // 10 + 1):
        I.extend(list(map(int, input().split())))

    S = []
    # 원소 20개마다 한 리스트에 담은 res 이차원 리스트를 만든다.
    res = [[] for _ in range(M // 20 + 1)]

    # I의 각 원소 x와 인덱스 i에 대해
    for i, x in enumerate(I):
        # S에 x를 정렬하면서 집어넣는다.
        insort_left(S, x)
        # i가 짝수일 때 (홀수 번째 입력일 때)
        if i % 2 == 0:
            # res[i // 20]에 S의 중간값을 집어넣는다.
            # 한 리스트에 원소가 10개씩 들어가도록 res의 인덱스를 i // 20로 지정 헀다.
            res[i // 20].append(str(S[i // 2]))

    # res의 각 리스트는 \n로 그 리스트의 원소는 공백으로 join 해서 출력한다.
    print("\n".join([" ".join(row) for row in result]))

아이디어 & 풀이

힙이 아닌 배열 이진 분할 알고리즘을 이용한다.

  • 파이썬의 bisect 라이브러리를 이용한다.
  • 각 입력을 bisect 라이브러리의 insort를 이용해 리스트 S에 삽입한 뒤 현재 S의 중간값을 적절히 출력한다.
  • bisect - Array bisection algorithm by Python Documentation