Tag: data structures

n, w, L = map(int, input().split())
trucks = list(map(int, input().split()))

bridge = deque([0] * w)
t = 0
cur_w = 0
i = 0

while i < n:
    t += 1
    cur_w -= bridge.popleft()
    if cur_w + trucks[i] <= L:
        bridge.append(trucks[i])
        cur_w += trucks[i]
        i += 1
    else:
        bridge.append(0)

t += w
print(t)

import heapq

N = int(input())

lessons = []
for _ in range(N):
    i, s, e = map(int, input().split())
    lessons.append((s, e, i - 1))

lessons.sort()
room_end = [(lessons[0][1], 1)]
result = [0] * N
result[lessons[0][-1]] = 1
room_cnt = 1

for s, e, i in lessons[1:]:
    # 가장 일찍 끝나는 방
    min_end, room_i = heapq.heappop(room_end)
    # 그 방을 사용 가능할 경우
    if min_end <= s:
        heapq.heappush(room_end, (e, room_i))
        result[i] = room_i
    # 사용 못하는 경우 -> 새로운 방
    else:
        # 원래대로 복구
        heapq.heappush(room_end, (min_end, room_i))
        # 새로운 방 만들기
        room_cnt += 1
        result[i] = room_cnt
        heapq.heappush(room_end, (e, room_cnt))

print(room_cnt)
print(*result, sep='\n')

cur_num = 2
stack = [1]
result = ['+']
for _ in range(n):
    target = int(input())
    if not stack:
        stack.append(cur_num)
        result.append('+')
        cur_num += 1
    while stack and stack[-1] < target:
        stack.append(cur_num)
        result.append('+')
        cur_num += 1
    if stack and stack[-1] == target:
        stack.pop()
        result.append('-')
        continue

if len(stack) == 0:
    print(*result, sep='\n')
else:
    print('NO')

import heapq

def nag_int(s):
    """음수 정수를 반환"""
    return -int(s)

TC = int(input())
for t in range(TC):
    N, M = map(int, input().split())
    importance_list = list(map(nag_int, input().split()))
    q = deque([(i, im) for i, im in enumerate(importance_list)])
    heapq.heapify(importance_list)

    cnt = 1
    cur_min = heapq.heappop(importance_list)

    while q:
        i, im = q.popleft()
        if i == M and cur_min == im:
            # M 번째 출력되면 끝
            break
        elif cur_min == im:
            # 출력 가능하면 다음으로
            cur_min = heapq.heappop(importance_list)
            cnt += 1
        else:
            # 출력 안되면 대기열 맨 뒤로
            q.append((i, im))
    print(cnt)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())
truth = list(map(int, input().split()))
truth_num = truth[0]
truth_people = set(truth[1:])

parent = list(range(N + 1))
parties = []

for _ in range(M):
    party = list(map(int, input().split()))
    party_people = party[1:]
    parties.append(party_people)
    
    # 같은 파티 사람들을 union
    for i in range(len(party_people) - 1):
        union(parent, party_people[i], party_people[i + 1])

# 진실을 아는 사람들과 같은 그룹인지 확인
result = 0
for party in parties:
    can_lie = True
    for person in party:
        for truth_person in truth_people:
            if find(parent, person) == find(parent, truth_person):
                can_lie = False
                break
        if not can_lie:
            break
    if can_lie:
        result += 1

print(result)

for i in range(1, n + 1):
    if not visited[i]:
        nodes = set()
        edges = set()

        # 사이클 확인
        if not dfs(i, 0, nodes, edges):
            continue

        # 사이클이 없고, 간선의 수가 노드의 수 - 1이면 트리
        if len(edges) == len(nodes) - 1:
            tree_count += 1

• 방문하지 않은 각 연결 요소에 대해 DFS 수행
• 사이클이 없고 간선 수 = 정점 수 - 1이면 트리로 카운트

if tree_count == 0:
    print(f"Case {case_num}: No trees.")
elif tree_count == 1:
    print(f"Case {case_num}: There is one tree.")
else:
    print(f"Case {case_num}: A forest of {tree_count} trees.")

• push X: deque.append(X)로 큐의 뒤에 원소를 추가
• pop: deque.popleft()로 큐의 앞에서 원소를 제거하고 반환
• size: len(deque)로 큐의 크기 반환
• empty: 큐가 비어있는지 확인
• front: deque[0]로 큐의 첫 번째 원소 접근
• back: deque[-1]로 큐의 마지막 원소 접근

모든 연산에서 큐가 비어있을 때의 예외 처리를 해주어야 한다.

from collections import deque
import sys

N = int(sys.stdin.readline().strip())

q = deque()

for i in range(N):
  cmd = sys.stdin.readline().strip().split()
  if cmd[0] == 'push':
    q.append(cmd[1])

  elif cmd[0] == 'pop':
    if len(q) != 0:
      print(q.popleft())
    else:
      print(-1)

  elif cmd[0] == 'size':
    print(len(q))

  elif cmd[0] == 'empty':
    if len(q) == 0:
      print(1)
    else:
      print(0)

  elif cmd[0] == 'front':
    if len(q) != 0:
      print(q[0])
    else:
      print(-1)
      
  elif cmd[0] == 'back':
    if len(q) != 0:
      print(q[-1])
    else:
      print(-1)

max_h = 0
pillar_list = [0] * 1001

max_loc = 0
for _ in range(N):
    loc, h = map(int, input().split())
    max_h = max(max_h, h)
    max_loc = max(max_loc, loc)
    pillar_list[loc] = h

# 왼쪽에서 시작
i_l = -1
cur = 0
ans = 0
while cur < max_h:
    i_l += 1
    cur = max(cur, pillar_list[i_l])
    ans += cur

# 오른쪽에서 시작
i_r = max_loc + 1
cur = 0
while cur < max_h:
    i_r -= 1
    cur = max(cur, pillar_list[i_r])
    ans += cur

if i_r == i_l:
    ans -= max_h
else:
    ans += max_h * (i_r - i_l - 1)

print(ans)

from queue import PriorityQueue

n = int(input())
pq = PriorityQueue()

for _ in range(n):
    num = int(input())
    pq.put(num)

result = 0

while pq.qsize() > 1:
    tmp = pq.get()
    num = pq.get()
    result += tmp + num
    pq.put(tmp + num)

print(result)

우선순위 큐에 입력으로 들어온 카드 뭉치의 크기를 삽입하고 반복문을 시작한다.

우선순위 큐의 첫 번째, 두 번째 원소를 빼내서 더해준다 (카드 뭉치를 합침). 그리고 이를 결과가 저장될 result 함수에 저장해준다 (합칠 때 비교한 횟수를 반영). 마지막으로 첫 번째와 두 번째 원소의 합을 다시 우선순위 큐에 넣어준다. 다시 넣어주면 합쳐진 카드 뭉치를 자연스럽게 다시 합칠 수 있다.