AndroidTeacher

문제 설명

https://www.acmicpc.net/problem/1655

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

풀이 과정

이 문제는 정렬로 풀면 시간초과 오류가 나기 때문에 우선순위 큐를 이용하여야 한다.

전체적인 접근 방식은

문제에서 구하고자 하는 값이 중간값이기 때문에

중간값보다 작은 값들은 leftHeap에, 큰 값은 rightHeap에 저장하는 방식이다.

풀이 과정은 다음과 같다.

① 중간값이라는 것은 주어진 N개의 수 중 중간에 위치한 값이기 때문에

값을 leftHeap과 rightHeap에 번갈아 넣어줌으로써 두 힙의 균형(개수)을 유지하도록 하여

leftHeap에서 pop을 했을 때 바로 중간값을 구할 수 있도록 한다.

② leftHeap은 최대힙으로, rightHeap은 최소힙으로 구성을 함으로써

leftHeap의 첫 원소를 중간값으로 만들 수 있다.

③ 이 때, rightHeap에 원소를 넣는 차례에 leftHeap보다 작은 값을 넣게 된다면

rightHeap에 중간값보다 큰 원소가 들어가게 되므로

leftHeap의 첫 원소와 rightHeap의 첫 원소를 교체하여 균형을 유지할 수 있도록 한다.

여기서,파이썬 코드 작성 시 주의해야 할 점은 입력 시 input()을 이용한다면 시간초과 오류가 발생하므로

sys.stdin.readline()을 이용하도록 하자.

import heapq
import sys

n = int(sys.stdin.readline())

leftHeap = []
rightHeap = []
for i in range(n):
    num = int(sys.stdin.readline())

    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -num)
    else:
        heapq.heappush(rightHeap, num)

    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftValue = heapq.heappop(leftHeap)
        rightValue = heapq.heappop(rightHeap)

        heapq.heappush(leftHeap, -rightValue)
        heapq.heappush(rightHeap, -leftValue)

    print(-leftHeap[0])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/7662

자세한 설명은 위 링크를 참고해주세요.

풀이 과정

우선순위 큐 두개를 놓고 풀었다.

일반 우선순위큐와는 다르게 최대값과 최소값 모두를 빼올 수 있는 우선순위큐를 만들어야 하기 때문에

하나는 최소값용 우선순위큐

다른 하나는 최대값용 우선순위큐를 만든다.

이 때, 주의해야 할 점은 최소값 우선순위큐에서 값을 제거한다면

마찬가지로 최대값 우선순위큐에서도 제거를 해서 두 우선순위의 상태를 맞춰주어야 한다는 점이다.

처음에 접근했던 방식은 최대값을 구할 때는 최댓값 우선순위큐에서 pop을 하고

최소값 우선순위큐의 마지막 원소를 삭제하는 식으로 구현을 했다.

하지만 heapq자체가 정렬되어 있는 상태가 아니기 때문에(Heap구조를 유지하지만 정렬되어있진 않음)

이 방식은 틀린 방식이었다.

그렇다고 PriorityQueue를 사용하자니, 첫 원소를 제외하고는 따로 삭제할 수 있는 방법이 없었다.

그래서 각각의 원소에 ID를 부여하여, 해당 원소가 삭제된 원소인지 아닌지를 판별하여

두 큐의 상태를 맞춰주었다.

예를 들어, 3이라는 원소가 삽입되었다가 최소값 큐에서 삭제된 상태라면

최대값 큐에서도 삭제된 상태여야 하기 때문에

최대값에서 검사를 할 때, 해당 원소의 상태가 True인지 False인지를 판별하여 실제 존재하는 원소인지 아닌지를 알 수 있게 되는 것이다.

import heapq

t = int(input())

for i in range(t):
    k = int(input())
    q1, q2 = [], []
    visited = [False] * k

    for j in range(k):
        com, num = input().split()

        if com == 'I':
            heapq.heappush(q1, (int(num), j))
            heapq.heappush(q2, (-int(num), j))
            visited[j] = True

        else:
            if num == '1':
                while q2 and not visited[q2[0][1]]:
                    heapq.heappop(q2)
                if q2:
                    visited[q2[0][1]] = False
                    heapq.heappop(q2)
            else:
                while q1 and not visited[q1[0][1]]:
                    heapq.heappop(q1)
                if q1:
                    visited[q1[0][1]] = False
                    heapq.heappop(q1)

    while q1 and not visited[q1[0][1]]:
        heapq.heappop(q1)
    while q2 and not visited[q2[0][1]]:
        heapq.heappop(q2)

    if not q1 or not q2:
        print("EMPTY")
    else:
        a = -q2[0][0]
        b = q1[0][0]
        print("%d %d" % (a, b))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/14235

크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다.

올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다.

하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다.

또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

이제 산타가 선물을 나눠줄 것이다.

차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들이 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

풀이 과정

우선순위큐를 이용하면 간단하게 해결할 수 있는 문제였다.

산타가 선물을 저장할 때는 우선순위 큐를 이용해 가장 가치가 높은 선물이 앞으로 오도록 하고

아이들을 만날 때 마다 큐의 가장 첫 요소를 꺼내어 주면 된다.

우선순위큐는 숫자가 낮은 값부터 저장이 되기 때문에

저장을 할 때는 -를 붙이고 꺼낼 때 다시 -를 붙여줌으로써

큰 숫자가 가장 앞에 오도록 하고 가장 먼저 꺼낼 수 있도록 할 수 있다.

import heapq

n = int(input())
gift = []

for i in range(n):
    a = list(map(int, input().split()))
    if a[0] == 0:
        if len(gift) == 0:
            print(-1)
        else:
            tmp = -heapq.heappop(gift)
            print(tmp)
    else:
        for j in range(a[0]):
            heapq.heappush(gift, -a[j+1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/11000

문제 설명

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

풀이 과정

이 문제에서 중요하게 생각해야 할 부분은,

현재 회의실의 종료시간과 다음 열릴 회의의 시작시간 과의 관계이다.

① 현재 회의실에서의 회의가 끝나는 시간보다 다음 회의의 시작시간이 빠르면

회의실을 하나 추가로 개설한다.

② 현재 회의실에서 회의가 끝나는 시간보다 다음 회의의 시작시간이 느리면

현재 존재하는 회의실에서 이어서 회의 개최가 가능하다.

이 두가지를 고려하면 된다.

먼저, 회의의 [시작, 끝] 시간을 세트로 하나의 리스트에 모두 입력받는다.

그리고 시작시간을 기준으로 정렬을 먼저 해준다. 그럼 시작시간이 빠른 순서대로 앞에 오게 된다.

그리고 첫 회의의 종료시간을 새로운 큐(room)에 먼저 넣어준다.

그럼 두 번째 회의부터 첫 회의와 비교를 하게 될텐데,

두 번째 회의의 시작시간이 첫 회의의 종료시간보다 빠르면 새로 회의실을 개최해야 하고

아니면, 기존 회의실을 사용하면 된다.

밑의 코드에서 기존 회의실을 사용하는 코드는 room에서 한번 pop을 해주고 새로운 회의시간을 push 해주는 것이다.

새로 회의실을 개설해야 하면, room에 새로운 회의의 종료시간을 push 해주면 된다.

단, 이 때 종료시간이 빠른 회의실부터 다음 회의를 이어서 개최해야 하기 때문에

우선순위 큐를 이용해 큐에 push를 해주어 큐가 정렬상태를 유지할 수 있도록 해준다.

import heapq
n = int(input())

q = []

for i in range(n):
    start, end = map(int, input().split())
    q.append([start, end])

q.sort()

room = []
heapq.heappush(room, q[0][1])

for i in range(1, n):
    if q[i][0] < room[0]: # 현재 회의실 끝나는 시간보다 다음 회의 시작시간이 빠르면
        heapq.heappush(room, q[i][1]) # 새로운 회의실 개설
    else: # 현재 회의실에 이어서 회의 개최 가능
        heapq.heappop(room) # 새로운 회의로 시간 변경을 위해 pop후 새 시간 push
        heapq.heappush(room, q[i][1])

print(len(room))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/11286

문제 설명

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

풀이 과정

이 문제는 두 가지 풀이방법을 이용하여 풀어보았습니다.

방법① 은 길이가 많이 간결한 방법으로

힙큐에 값을 넣을 때 (절대값, 원래값) 쌍으로 넣어줌으로써

절대값을 기준으로 정렬을 할 수 있게 하였습니다.

import sys
import heapq

n = int(input())
q = []

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if a != 0:
        heapq.heappush(q, (abs(a), a))
    else:
        if not q:
            print(0)
        else:
            print(heapq.heappop(q)[1])

방법 ② 은 첫 번째 방법보다 풀이가 다소 긴 감이 있지만

입력값이 양수인지 음수인지에 따라 서로 다른 공간에 저장을 하였습니다.

풀이 방법과 사고과정은 좀 더 복잡할 수 있지만,

간혹 우선순위큐에 익숙치 않은 분들은 요소를 두 개 이상 넣는 것을 모르고 계신 경우도 있어서

이 풀이를 참고하시면 될 것 같습니다!

import sys
import heapq

n = int(input())
q1 = [] # 음수를 넣을 큐
q2 = [] # 양수를 넣을 큐

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if a < 0:
        heapq.heappush(q1, -a) # 절대값이 작은게 앞에 와야 하므로
    elif a > 0:
        heapq.heappush(q2, a) # 양수이므로 그대로 최소힙으로 구현
    else:
        if not q1:
            if not q2:
                print(0)
            else:
                print(heapq.heappop(q2))
        elif not q2:
            print(-heapq.heappop(q1))

        else:
            tmp1 = -heapq.heappop(q1)
            tmp2 = heapq.heappop(q2)

            if abs(tmp1) > abs(tmp2):
                print(tmp2)
                heapq.heappush(q1, -tmp1)

            else:
                print(tmp1)
                heapq.heappush(q2, tmp2)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !