[구름톤 챌린지]블로글학습일기 3주차(2)

우리 MZ공대생 돋보기를 들고 다니기 시작했다. 귀가없어서 관자놀이에 붙인 연필... ㅋㅋㅋ

14일차 : 작은 노드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())

graph = [[] for _ in range(N+1)]

# 노드 방문 체크
visited = [0]*(N+1)

for _ in range(M):
    a, b = map(int, input().split())
    # 양방향 간선 연결
    graph[a].append(b)
    graph[b].append(a)

# 작은 것 부터 (오름차순)
for i in range(1, N+1):
    graph[i].sort()

visited[K] = 1
cnt = 1

for _ in range(N):
    for next_node in graph[K]:
        if visited[next_node] == 0:
            visited[next_node] = 1
            K = next_node
            cnt += 1
            break

print(cnt, K)

가장 작은 노드부터 순서대로 입력 받는다는 보장이 없기 때문에, 오름차순으로 정렬함 인접행렬로 입력받을 시 정렬할 필요가 없을듯하다.

15일차 : 과일 구매

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

arr = []

result = 0
for _ in range(N):
    # 각 조각 포만감, 과일 가격, 포만감
    P, C = map(int,input().split())
    arr.append((C//P, P, C))

# 각 조각 포만감이 높은순, 같으면 가격이 낮은 순
arr.sort(key= lambda x:(-x[0], x[1]))

# 시간 복잡도 O(N^2)에서 O(N)으로 개선
# ---------------------------------------
# for i in range(N):
#     for j in range(arr[i][1]):
#         if K == 0:
#             break;

#         K -= 1
#         result += arr[i][0]
# ---------------------------------------

for i in range(N):
    # 각 조각의 포만감 * (해당 과일을 최대로 먹을 수 있는 조각 수)를 결과에 더함
    max_pieces = min(K, arr[i][1])
    result += arr[i][0] * max_pieces
    K -= max_pieces
    
    if K == 0:
        break        

print(result)

가진돈 (K)와 과일의 가격(P)를 비교해 가진돈이 더 많으면 과일 전체를 구매하고, 포만감을 더해줌, 가진돈이 적게 되면 가진돈(K)만큼 과일 피스의 포만감 더해줌.

시간 복잡도를 고려하지 않고 O(n^2) 2중반복문으로 순회하가다 시간초과로 O(n)시간복잡도로 다시 구현했다.