(BOJ1655 가운데를 말해요

• tags : (algorithm

  No matching post could be found

  - (heap
• 문제 링크 : https://www.acmicpc.net/problem/1655
• 풀이 링크
  • Python

• 입력을 순서대로 받으며 전체 입력에서 중간값을 계속 출력해야 한다.
• 입력값을 계속 정렬한다면 아마 시간초과가 날 것으로 보인다.
  • 특히 시간 제한을 가진 문제라 더욱 그렇다.
• 그렇기 때문에 입력값들 중 중간값을 기준으로 작은 값, 큰 값을 구분하ㅓ여 가지고 있으면 좋다.
  • 그리고 지속적으로 값을 넣고 빼기 위하여 heap구조를 활용하면 편하게 처리할 수 있다.

N = II()
mid = II()
ans = f"{mid}\n"
small_val, large_val = [], []

• 풀이를 위한 초기 설정
• 처음 2개 값을 입력 받는다.
  • N은 입력의 개수이고, 주어진 입력 중 첫 번째 값은 mid값으로 둔다.
• 다음 중간값을 기준으로 더 작은 값, 큰 값을 저장할 heap을 만들어둔다.

for i in range(1, N):
    k = II()
    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)
    ans += f"{mid}\n"

• 문제 풀이 코드 부분
• 우선, 총 N개의 입력이 주어지는데, 처음 한개 입력을 mid값으로 사용했으므로, N-1개 값만 입력을 받는다.
• 각 입력을 받고, 입력 받은 수의 갯수에 따라 경우의 수를 나누어 처리한다.
  • 만약 i가 홀수라면, small_val, large_val 두 개의 heap에 저장된 수의 갯수가 같다.
    • 이 경우, large_val에 1개 값이 더 저장되도록 한다.
  • i가 짝수라면 이미 large_val에 1개 값이 더 많이 저장되어 있다.
    • 그래서 small_val, large_val에 저장될 숫자의 갯수가 같아지도록 한다.