[백준] CLASS 3 달성하기 3일차

이진규·2022년 7월 11일
1

백준(PYTHON)

목록 보기
49/115

1. 팩토리얼 0의 개수(수학)

링크 : https://www.acmicpc.net/problem/1676

from sys import stdin
input = stdin.readline

n = int(input())
answer = 0
num = 1

for i in range(2, n+1): # 팩토리얼 연산
    num *= i

num = str(num)
for i in range(len(num)-1, 0-1, -1): # 문자열로 변환 후 뒤에서 부터 0의 개수 세기
    if num[i] == '0':
        answer += 1
    else:
        break

print(answer)

2. 숨바꼭질(BFS)

링크 : https://www.acmicpc.net/problem/1697

from sys import stdin
from collections import deque
input = stdin.readline

n, k = map(int, input().split())

def bfs(v):
    step = [0] * (100000+1)
    q = deque([v])

    while q:
        node = q.popleft()

        if node == k:
            print(step[node])
            break

        for x in (node-1, node+1, node*2):
            if 0 <= x <= 100000 and not step[x]:
                step[x] = step[node] + 1
                q.append(x)

bfs(n)

3. 듣보잡(집합 자료형, 정렬)

링크 : https://www.acmicpc.net/problem/1764

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
hear_list = set()
look_list = set()
answer = set()

for _ in range(n):
    hear_list.add(input().rstrip())

for _ in range(m):
    look_list.add(input().rstrip())

answer = hear_list & look_list # 집합 자료형의 교집합

print(len(answer))
answer = list(answer) # 사전순으로 출력해야 하기 때문에 집합 자료형은 순서가 없어 정렬이 불가능해 리스트로 바꾸어서 정렬 진행
answer.sort()
for i in answer:
    print(i)

4. 종이의 개수(★분할정복)

링크 : https://www.acmicpc.net/problem/1780

처음 풀이한 코드

from sys import stdin
input = stdin.readline

n = int(input())
pan = [ list(map(int, input().split())) for _ in range(n) ]
answer = [0, 0, 0] # [0의 개수, 1의 개수, -1의 개수]

def div_and_con(x, y, l):
    num = pan[x][y] # 숫자를 임시로 저장

    for i in range(x, x+l):
        for j in range(y, y+l):
            
            if pan[i][j] != num: # 임시로 저장한 숫자와 일치하지 않을 시 9등분 진행
                l //= 3
                div_and_con(x, y, l)
                div_and_con(x, y+l, l)
                div_and_con(x, y+l+l, l)
                div_and_con(x+l, y, l)
                div_and_con(x+l, y+l, l)
                div_and_con(x+l, y+l+l, l)
                div_and_con(x+l+l, y, l)
                div_and_con(x+l+l, y+l, l)
                div_and_con(x+l+l, y+l+l, l)
                return

	# 이 구문이 수행되는 경우는 위의 반복문을 통과하여 더이상 분할할 것이 없을 때 수행된다.
    answer[num] += 1 

div_and_con(0, 0, n)

print(answer[-1])
print(answer[0])
print(answer[1])

깔끔하게 개선한 코드

from sys import stdin
input = stdin.readline

n = int(input())
pan = [ list(map(int, input().split())) for _ in range(n) ]
answer = [0, 0, 0] # [0의 개수, 1의 개수, -1의 개수]

def div_and_con(x, y, l):
    num = pan[x][y] # 숫자를 임시로 저장

    for i in range(x, x+l):
        for j in range(y, y+l):

            if pan[i][j] != num: # 임시로 저장한 숫자와 일치하지 않을 시 9등분 진행
                l //= 3
                for k in range(3):
                    for h in range(3):
                        div_and_con(x+(k*l), y+(h*l), l)
                return
	
    # 이 구문이 수행되는 경우는 위의 반복문을 통과하여 더이상 분할할 것이 없을 때 수행된다.
    answer[num] += 1

div_and_con(0, 0, n)

print(answer[-1])
print(answer[0])
print(answer[1])

5. 최소 힙(힙 자료구조)

링크 : https://www.acmicpc.net/problem/1927

import heapq
from sys import stdin
input = stdin.readline

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

for _ in range(n):
    x = int(input())

    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))

    else:
        heapq.heappush(heap, x)

6. 회의실 배정(그리디, 정렬)

링크 : https://www.acmicpc.net/problem/1931

import heapq
from sys import stdin
input = stdin.readline

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

for _ in range(n):
    st, en = map(int, input().split())
    meet.append((st, en))

meet.sort(key=lambda x : (x[1], x[0]))

now = 0 # 현재 회의 진행하는 시간
cnt = 0 # 회의 진행 횟수
for st, en in meet:
    if now <= st:
        now = en
        cnt += 1

print(cnt)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글