[백준/Python] 11279. 최대 힙 & 11724. 연결 요소의 개수

1. 백준 11279. 최대힙

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

11279번: 최대 힙

문제

  널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

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

입력

  첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

  입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

from heapq import heappop, heappush
import sys

n = int(sys.stdin.readline())
heap = []

for _ in range(n):
    temp = int(sys.stdin.readline())
    
    if temp == 0:
        if len(heap) == 0:
            print(0)
        else: print(-heappop(heap))
    else:
        heappush(heap, -temp)

• python의 heapq는 최소힙만을 지원하기 때문에, 최대힙을 구현하기 위해서는 부호를 반대로 push한 다음 pop할 때 다시 - 부호를 붙여서 원래의 수가 나올 수 있도록 구현하면 된다는 것을 배웠다.
• 처음에 그냥 input으로 입력받으니 시간초과가 나서 sys로 바꾸니 바로 통과됐다.
• input을 통한 입력이 생각보다 많은 시간을 잡아먹는다는 것을 한 번 더 실감했다.

---

 

2. 백준 11724. 연결 요소의 개수

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

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())
visited = [0 for _ in range(n+1)]
node = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    node[a].append(b)
    node[b].append(a)

queue = deque([])

def bfs():
    while queue:
        check = queue.popleft()
        visited[check] = 1

        for c in node[check]:
            if visited[c] == 1:
                continue
            else:
                queue.append(c)
                bfs()

count = 0

for i in range(1, n+1):
    if visited[i] == 0:
        queue.append(i)
        bfs()
        count += 1
    else:
        continue

print(count)

• bfs를 생각하고 구현했다. 
• 이번엔 그냥 미리 sys로 바꿔서 제출했다. 앞으로 이걸 더 습관화해야겠다.