우주의 IT 소행성

나의 코드

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

n, m = map(int, input().split())
data = [input() for _ in range(n)]
s = [input() for _ in range(m)]

count = 0
data = Counter(data)

for i in s:
    if data[i]:
        count += 1

print(count)

풀이 방법

Collections의 Counter를 이용

나의 코드

n, m = map(int, input().split())
data = sorted(list(map(int, input().split())))


def binary(arr, start, end):
    if start > end:
        return end

    mid = (start + end) // 2
    count = 0
    for i in arr:
        if mid < i:
            count += (i - mid)

    if count == m:
        return mid
    elif count < m:
        return binary(arr, start, mid - 1)
    else:
        return binary(arr, mid + 1, end)

print(binary(data, 0, max(data)))

풀이 방법

이분탐색 랜선 자르기 문제와 유사한 문제

나의 코드

k, n = map(int, input().split())
data = [int(input()) for _ in range(k)]
data.sort()

def binary(arr, start, end):
    if start > end:
        return end

    mid = (start + end) // 2
    lines = 0

    for i in data:
        lines += i // mid

    if lines >= n:
        return binary(arr, mid + 1, end)
    else:
        return binary(arr, start, mid - 1)


print(binary(data, 1, data[-1]))

풀이 방법

binary-search 를 응용하여 풀이

나의 코드

from collections import deque

n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
sonic = deque()
water = deque()
count = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == '*':
            water.append((i, j))
            visited[i][j] = True
        elif graph[i][j] == 'S':
            sonic.append((i, j))
            visited[i][j] = True
        elif graph[i][j] == 'X':
            visited[i][j] == True

while sonic:
    for _ in range(len(water)):
        wx, wy = water.popleft()
        for i in range(4):
            nx = wx + dx[i]
            ny = wy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.':
                    water.append((nx, ny))
                    graph[nx][ny] = '*'
                    visited[nx][ny] = True
    count += 1

    for _ in range(len(sonic)):
        sx, sy = sonic.popleft()
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == '.' and not visited[nx][ny]:
                    sonic.append((nx, ny))
                    visited[nx][ny] = True
                elif graph[nx][ny] == 'D':
                    print(count)
                    exit()
print("KAKTUS")

물이 차오르는 것 + 고슴도치가 이동하는 것을 함께 1사이클로 생각하는 bfs 문제.