study

# 절댓값 힙. 처음의 값을 기억해야하지만 정렬은 절댓값으로 해야함. from heapq import * import sys n = int(input()) # 입력 횟수 x_ls = [int(sys.stdin.readline()) for _ in range(n)] # 연산 리스트 heap = [] for x in x_ls: if x == 0: # x가 0이면 = 출력해야함 if len(heap) == 0: # 힙에 아무것도 없으면 0 출력 print(0) else:# 힙의 길이가 1개 이상이면 절댓값이 가장 작은 값을 출력한다 _, x = heappop(heap) print(x) else: # x가 0이 아닐때는 힙에 x의 절댓값과 x를 넣어줌 heappush(heap, (abs(x), x)) 생각보다 ..

from heapq import * n, m = map(int, input().split()) cards = [] # 카드를 넣어줄 힙 for num in list(map(int, input().split())): # 숫자들을 힙에 넣어줌 heappush(cards, num) for i in range(m): # m만큼 카드 합체하기 x = heappop(cards) # 1번째 작은 값 y = heappop(cards) # 2번째 작은 값 heappush(cards, x + y) # 기존의 카드가 빠지고 합이 추가됨 *2 heappush(cards, x + y) print(sum(cards)) # 카드의 총합을 출력 입력되는 카드들에 특정한 연산을 하고 만들 수 있는 가장 작은 점수를 계산해 리턴하는 문..

from heapq import * n = int(input()) heap = [] for _ in range(n): for i in list(map(int, input().split())): # 리스트를 돌면서 원소를 힙에 넣어줌 if len(heap) < n: # 만약 힙의 요소가 n개 미만이라면 i를 힙에 추가 heappush(heap, i) else: # 힙의 요소가 n개 이상일때 if heap[0] < i: # 만약 최소값이 i보다 작다면 heappop(heap) # 현재 힙의 최소값을 제거 heappush(heap, i) # 현재 요소를 힙에 추가 print(heap[0]) 처음에는 최대 힙을 구하고 n번째가 될때까지 pop을 반복하는 코드를 짰었다. 하지만 결과는.....^^ 입력값이 n^2..

# 한번 입었던 조합은 안됨 = 중복 안됨 # 의상의 분류와 의상들이 주어졌을때 중복 없이 만들 수 있는 조합의 수 # 옷의 종류별로 분류. 각 종류에 대해 (해당 종류의 옷 개수 + 안입는 경우(1))을 종류만큼 곱해주고 아무것도 안입는 알몸인 경우 1가지를 빼준다 import sys case = int(input()) for _ in range(case): # 케이스만큼 반복 n = int(input()) # 의상 수 clothes = {} for _ in range(n): name, type = sys.stdin.readline().rstrip().split() if type in clothes: # 의상의 종류별 총 개수를 딕셔너리에 저장 clothes[type] += 1 else: clothes..

1. 힙 (Heap) 정해진 우선 순위에 따라 원소를 O(log n)에 추가 / 삭제가 가능한 자료구조. 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조이다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있어서, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 파이썬에서는 heapq 라이브러리를 사용해 구현할 수 있다. 파이썬의 heapq 라이브러리는 최소값을 우선 순위로 하는 힙을 제공한다. 기본 연산 push : 힙에 새로운 원소 추가 pop : 힙에서 가장 우선 순위가 빠른 원소를 추출하고 그 값을 반환 heapq 라이브러리 heapify : 리스트를 최소 힙으로 변환 heappush : 힙에 원소 추가 ..

# 문자열 길이만큼 반복 # stack 사용 # 맨끝에서 폭발문자열의 길이만큼 체크했을때 폭발문자열이 있다면 그만큼 삭제 # 반복믄 끝나면 모든 문자열을 붙여서 리턴 # stack 길이가 0이면 FRULA 출력 str = input() explode = list(input()) stack = [] for s in str: # 문자열 길이만큼 반복 stack.append(s) # stack에 글자 추가 # stack의 길이가 폭발문자열 길이 이상이고 stack의 끝부분에 폭발문자열이 있다면 if len(stack) >= len(explode) and stack[-len(explode):] == explode: del stack[-len(explode):] # stack에 있는 폭발문자열 제거 if not ..

# 오큰수 = i보다 오른쪽에 있으면서 가장 큰수들 중 i와 제일 가까운(왼쪽)이 있는 수 # 오큰수가 없다면 -1 # 수열 개수만큼 반복 # stack에는 0번째 수가 들어있다. 0번째 수와 1번째 수 비교 # 0번과 1번 비교시 1이 크다면 result에 현재 인덱스에 큰 값 추가 # 크지 않다면 pop. n = int(input()) num_ls = list(map(int, input().split())) result = [-1 for _ in range(n)] stack = [] # 각 인덱스를 저장 for i in range(n): # n만큼 반복 while stack and num_ls[i] > num_ls[stack[-1]]: # 현재 요소와 이전 요소들을 비교. 현재 요소가 이전 요소보다 ..

# stack # 탑 개수만큼 반복 # 레이저가 발사되는 탑의 이전 탑이 더 높거나 같아야 수신 가능. # 현재 탑과 이전 요소들을 비교해서 현재 탑보다 낮다면 건너뛰기. # 높거나 같다면 해당 요소 인덱스를 결과에 추가. n = int(input()) towers = list(enumerate(map(int, input().split()))) # 인덱스 + 탑높이 result = [0 for _ in range(n)] # 결과 배열 stack = [] # 왼쪽 탑과 비교해줄 stack for idx, height in towers: while stack: # stack에 값이 있을때. 맨 왼쪽은 수신이 안되니까 그냥 넘어감. top_idx, top_height = stack[-1] # 현재 탑에서 왼쪽..

""" - 자료구조 덱 사용 * 문제 정리 - 출력값 : 터진 풍선의 번호 나열 - 1번 풍선 터짐 -> 해당 값만큼 이동 -> 풍선 터지고 이동... - 값이 양수면 오른쪽으로 음수이면 왼쪽으로 이동. 이미 터진 풍선은 제외. * 개념 정리 - enumerate : 순서가 있는 자료형을 받았을때 인덱스와 값을 포함해 리턴 - deque.rotate() : 원형 큐를 회전. 음수는 반시계로 회전, 양수는 시계방향으로 회전. """ from collections import deque n = int(input()) balloons = deque(enumerate(map(int, input().split()))) order = [] while balloons: idx, paper = balloons.popl..

""" - 자료구조 큐 사용 * 문제 정리 - 출력값 : 각 문서의 중요도와 순서에 따라 인쇄가 될때, N개중 M번째의 문서는 몇번째로 출력되는가? - 인쇄 조건 - 현재 큐의 가장 앞에 있는(0번째) 문서의 중요도 확인 - 다른 문서들 중 중요도가 더 높은것이 있는지?(= 현재 문서의 중요도가 가장 높은지?) - 더 높은 것이 없다면 출력 - 그렇지 않다면 맨 뒤로 재배치 - 0번째 문서의 중요도 확인 반복 * 수도 코드 - 중요도들을 큐에 추가 - 찾을 문서의 현재 위치를 기억 - 인쇄 조건 확인 => 0번째 문서가 중요도의 최대값과 같은지? - 같다면 출력 + 1. 찾을 위치값 -1. - 다르다면 0번째 문서를 제거 후 맨 뒤에 다시 추가. 찾을 문서의 위치값 조정. - 찾을 문서의 위치값이 0이 ..