study/Algorithm

# 이분탐색 # 심사대 n개 사람수 m명 시간 t # 탐색 범위는 심사에 걸리는 시간. t의 최소값 / 최대값 * 인원수 import sys n, m = map(int, input().split()) t = [int(sys.stdin.readline()) for _ in range(n)] start, end = min(t), max(t) * m result = end # 탐색을 진행하며 더 작은 값을 찾아가기때문에 현재 최대값으로 초기화해줌 while start = m: # 만약 심사할수있는 사람이 m보다 크다면 = 탐색할 범위의 값을 줄여야함 end = mid - 1 result = mid # 중간값을 결과에 갱신 else: # 심사할 수 있는 사람이 m보다 작다면 = 탐색 범위의 값을 늘려야함 sta..

# 2017481620 # 정렬 사용. # 좌표 압축 -> 주어진 x들의 값을 오름차순으로 정렬했을때의 인덱스값. # 같은 숫자가 있을 수 있으니 셋으로 정리 n = int(input()) numbers = list(map(int, input().split())) sort_nums = sorted(set(numbers)) dict = {sort_nums[i] : i for i in range(len(sort_nums))} # key : numbers의 각 값, value : 오름차순 정렬시 각 값의 인덱스 for j in range(len(numbers)): numbers[j] = dict[numbers[j]] print(' '.join(map(str, numbers))) https://www.acmic..

# 이분탐색. m만큼 자르는데 필요한 높이를 이분탐색으로 찾기 # 필요한 높이의 최소값은 1 최대값은 제일 높은 나무의 높이 # 나무의 높이가 중간값보다 크다면 값을 빼주고 총합을 구함. # 총합이 m과 같다면 중간값이 결과값. n, m = map(int, input().split()) trees = sorted(list(map(int, input().split()))) start, end = 1, max(trees) # 나무 높이를 이진 탐색하기 위해 정한 범위 while start = mid: # 나무 높이가 벌목 높이보다 높다면 temp += i - mid # 잘라낸 길이만큼 temp에 더함 if temp >= m: #잘라낸 길이가 m보다 크다 = 벌목 높이를 높여야함 start = mid + 1 ..

# 총 시간의 최소값을 구해야함 # 2번이 필요한 시간 = 1번 시간 + 2번 시간. 3번은 1번 + 2번 + 3번 ... # 오름차순으로 정렬 후 0번부터 현재값까지의 합을 결과값에 더해줌 n = int(input()) times = sorted(list(map(int, input().split()))) result = 0 for i in range(len(times)): result += sum(times[0:i+1]) print(result) 정렬을 활용하는 간단한 문제! 더해줘야하는 값은 sum과 슬라이싱을 사용해주었다. https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 ..

from heapq import * n = int(input()) heap = [int(input()) for _ in range(n)] # 요소들 힙에 추가 heapify(heap) result = 0 while len(heap) > 1: # 힙에 더이상 더할 요소가 남지 않을때까지 x = heappop(heap) # 첫번째 작은 값 y = heappop(heap) # 두번째 작은 값 heappush(heap, x + y) # x + y 의 합을 다시 힙에 추가 result += x + y print(result) 문제 그대로 코드를 썼다. 최소값 순으로 두 값을 더하고 그 합을 남은 값과 다시 더하는 방식으로 구현했다. 힙에 더이상 더할 값이 없을때까지 반복문을 돌리게 하고 첫번째로 작은 값과 두번째..

# 절댓값 힙. 처음의 값을 기억해야하지만 정렬은 절댓값으로 해야함. 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..

# 문자열 길이만큼 반복 # 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 ..