IT-garden

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한조건

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

나의 풀이

import heapq

def solution(jobs):
    jobs=sorted(jobs, key = lambda x: (x[0],x[1]))
    heap=[] # 힙
    
    t = jobs[0][1] + jobs[0][0] # 전체 시간
    m = t - jobs[0][0] # 요청에서 종료까지
    i = 1
    
    while True:
        if i == len(jobs):
            break
            
        if jobs[i][0] < t: # 작업 중에 요청이 들어오는 것
            heapq.heappush(heap,[jobs[i][1],jobs[i][0]])
            i += 1
        else: # 작업이 끝나고 요청이 들어오는 것
            try: # 실행할 작업이 있는지 확인
                start,h=heapq.heappop(heap) 
                t += start # 전체 시간에 더하기
                m += t - h # 요청에서 종료까지 구해 더하기
            except: # 작업을 수행하고 있지 않은 경우
                t = jobs[i][0] + jobs[i][1] # 시간 새로 설정
                m += jobs[i][1] # 작업 소요시간 더하기 
                i += 1
                
    while True: # heap에 남아있는 것들을 처리하기 위한 무한 반복
        try:
            start,h=heapq.heappop(heap)
            t += start  # 전체 시간에 더하기
            m += t - h # 요청에서 종료까지 구해 더하기
        except:
            break
            
    return m//len(jobs) # 평균 시간

1. heapq을 이용하여 문제를 풀었습니다.
2. 예시를 통해 해당 시점으로부터 처리할 수 있는 작업들 중 가장 작업 소요시간이 작은 작업부터 해야 평균을 가장 줄일 수 있다는 것을 알 수 있습니다.
3. jobs를 오름차순으로 정렬하고 하나의 작업을 수행해 걸린 전체 시간(t)과 요청에서 종료까지 걸린 시간 m을 구합니다.
4-1. 무한 루프를 통해 작업이 진행 중에 새로운 작업이 들어오면 heapq에 넣습니다.
4-2. 그렇지 않을 경우 heapq에 값이 있다면 최소힙을 제거하고 t와 m을 계산합니다. heapq에 값이 없다면 t를 새로 설정하고 t와 m을 계산합니다.
5. 무한 루프가 끝나고 아직 heapq에 값이 있다면 heapq의 값들을 계산하고 요청부터 종료까지 걸린 시간의 평균을 리턴합니다.

프로그래머스 '디스크 컨트롤러' : https://programmers.co.kr/learn/courses/30/lessons/42627

문제 설명

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

제한조건

• stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
• stock과 k는 2 이상 100,000 이하입니다.
• dates의 각 원소는 1 이상 k 이하입니다.
• supplies의 각 원소는 1 이상 1,000 이하입니다.
• dates와 supplies의 길이는 1 이상 20,000 이하입니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
• dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
• 밀가루가 바닥나는 경우는 주어지지 않습니다.

입출력 예

입출력 예 설명

• 현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.
• 4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.
• 따라서 총 2회의 밀가루를 공급받으면 됩니다.

나의 풀이

import heapq

def solution(stock, dates, supplies, k):
    c=0
    h=[]
    s=0
    while stock < k:
        for i in range(s,len(dates)):
            if stock >= dates[i]:
                heapq.heappush(h,-supplies[i])
                s =i+1
            else:
                break
        stock -= heapq.heappop(h)
        c += 1
    return c

1. heapq에서 최대힙을 이용합니다.
2. stock이 k보다 작은 경우 while문을 실행합니다.
2-1. stock보다 작은 날짜들을 heapq에 넣습니다. 최대힙을 만들기 위해 -를 추가합니다.
2-2. heapq에서 가장 작은 값을 stock에서 뺍니다.(최대힙을 stock에 더하는 것)
2-3. 밀가루 공급받은 횟수를 1 추가합니다.
3. r를 리턴합니다.

프로그래머스 '라면공장' : https://programmers.co.kr/learn/courses/30/lessons/42629

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한조건

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

3. 모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

나의 풀이

import heapq

def solution(scoville, K):
    
    heapq.heapify(scoville)
    c = 0
    
    while True:
        if scoville[0] >= K:
            return c
        elif scoville[0] < K and len(scoville) == 1:
            return -1
        else:
            a = heapq.heappop(scoville) + ( heapq.heappop(scoville) * 2 )
            heapq.heappush(scoville, a)
            c += 1

1. heapq에서 최소힙을 이용합니다.

2. 힙의 첫번째 요소(가장 맵지 않은 스코빌 지수 요소)와 두번째요소(두번째로 맵지 않은 스코빌 지수 요소)를 이용해 새로운 음식을 만들어 힙에 넣습니다.

3. 힙의 첫번째 요소가 K보다 큰 경우 횟수를 출력합니다.

4. 힙의 요소가 1개밖에 남지 않고 첫번째 요소가 K보다 작은 경우 -1을 출력합니다.

5. 2번 과정을 반복하다 3번이나 4번을 충족할경우 해당 값을 리턴하고 종료합니다.

프로그래머스 '더 맵게' : https://programmers.co.kr/learn/courses/30/lessons/42626

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            ab, c= heapq.heappop(h)
            print(c)
        else:
            print(0)
    else:
        heapq.heappush(h, (abs(i),i))

heapq에 값을 (abs(i), i)로 저장합니다.

abs(i)를 통해 절대값이 작은 것부터 heapq에 넣어서 절대값이 작은 것이 앞에 올 수 있게 합니다.

i는 그대로 넣어서 절대값이 같더라도 i가 작은 것이 앞에 올 수 있게 합니다.

백준 알고리즘 11286번 : www.acmicpc.net/problem/11286

문제

널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            print(-heapq.heappop(h))
        else:
            print(0)
    else:
        heapq.heappush(h, -i)

최소힙과 반대로 -를 넣고 출력합니다.

백준 알고리즘 11279번 : www.acmicpc.net/problem/11279

문제

널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            print(heapq.heappop(h))
        else:
            print(0)
    else:
        heapq.heappush(h, i)

백준 알고리즘 1927번 : www.acmicpc.net/problem/1927