[백준] 2606, 2805 - Python3

2805. 나무 자르기

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

내 풀이 - 시간 초과 (Python3) / 통과 (PyPy3)

from sys import stdin
import collections

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

total = sum(trees)
trees.sort()
count = collections.Counter(trees)

if total == M:
    print(0)
else:
    idx = 0
    num = N
    if trees[idx] == 0:
        idx += count[0]
        num -= count[0]
    for t in range(1, max(trees)+1):
        if total - num < M:
            break
        total -= num 
        if t == trees[idx]:
            idx += count[t]
            num -= count[t]

    print(t-1)

나무들을 높이 1 씩 잘라감

나무의 전체 높이 합이 M 일 경우 자를 필요가 없으므로 print 0

나머지는 정렬하고
같은 높이의 나무를 알기 위해 Counter 를 구해줌

0 높이의 나무는 미리 제외 => idx, num update

1 부터 최대 높이까지 넉넉하게 범위를 잡고
높이 1 씩 나무를 잘라준다
=> total - 자를 수 있는 나무의 개수

M 보다 작아지면 더 자를 수 없으므로 break

현재 높이가 주어진 나무의 높이와 같아지면
그 다음부턴 해당 나무는 자를 수 없으므로 idx, num update
=> 중복일 경우를 고려해서 count 값만큼 +-

PyPy

• JIT 컴파일러가 포함 되어있어 일반적으로 Python 보다 속도가 빠르다
• Python 보다 메모리 사용량이 많다

따라서 Python3 와 PyPy3 를 적절하게 섞어가며 사용해야할 듯

하지만 이분 탐색을 사용하는게 정석!!!

내 풀이 2 - 시간 초과 (Python3) / 통과 (PyPy3)

from sys import stdin

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

total = sum(trees)
trees.sort()

l = 0
r = max(trees)

while l <= r:
    m = (l+r) // 2

    tmp = 0
    for i in range(N):
        if trees[i] >= m:
            break
        tmp += trees[i]	# m 보다 작은 값들
    tmp += m*(N-i)	# 현재 높이 * m 보다 큰 값들의 개수
    
    if total - tmp < M:
        r = m-1
    else:
        l = m+1

print(l-1)

이분 탐색 이용

"m 보다 작은 값들" 과 "현재 높이 * m 보다 큰 값들의 개수" 는 total 에서 빼줌
그 값이 M 보다 작으면 더 작게 잘라야하므로 r 변경
크거나 같으면 더 크게 자르기 위해 l 변경

다른 사람의 풀이

from sys import stdin

N, M = map(int, stdin.readline().split())
trees = list(map(int, stdin.readline().split()))

l = 0
r = max(trees)

while l <= r:
    m = (l+r) // 2

    tmp = 0
    for i in range(N):
        if trees[i] >= m:
            tmp += trees[i] - m
    
    if tmp < M:
        r = m-1
    else:
        l = m+1

print(r)

더 깔끔한 이분 탐색

나무들을 정렬하지 않고
자를 수 있는 나무들만 현재 높이만큼 잘라서 tmp 에 저장한 후 M 과 비교

2606. 바이러스

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

내 풀이 - 성공

from sys import stdin
import collections

N = int(stdin.readline())
C = int(stdin.readline())
network = {i:[] for i in range(1, N+1)}

for i in range(C):
    a, b = map(int, stdin.readline().split())
    network[a].append(b)
    network[b].append(a)

computers = [1]*(N+1)
computers[0] = 0

queue = collections.deque([1])

while queue:
    q = queue.popleft()
    computers[q] = 0
    for n in network[q]:
        if computers[n]:
            queue.append(n)

print(computers.count(0)-2)

network 에 서로 연결된 컴퓨터들 저장
computers 에 웜 바이러스 감염 여부 저장
0 번째 인덱스는 사용하지 않으므로 0 으로 초기화

1 번 컴퓨터부터 감염되므로 queue 에 1 저장
하나씩 pop 해서 감염 표시 => computers[q] = 0
연결된 컴퓨터들을 queue 에 append

최종적으로 감염된 컴퓨터의 수는 0 의 개수 - 2
(2 => 의미없는 0 번째 & 시작 값인 1 번째)