[ProblemSolving] 프로그래머스KIT - 더 맵게, 디스크 컨트롤러, 이중우선순위큐(heap)

문제 설명은 생략하겠습니다. 링크를 클릭하세요.

더맵게

나의 풀이

스코빌 지수가 가장 낮은 2개를 골라 연산해야 하므로, 힙을 이용하여 구현했다.

힙은 내부적으로 가장 작은 값이 상단에 위치하기 때문에 값을 꺼내는 과정이 편리하여 사용했다.

heap 문법

import heapq
heapq.heapify(리스트) : 리스트를 힙으로 변환
heapq.hoappop(리스트) : 힙의 가장 작은 값 삭제
heapq.heappush(리스트, 푸시할 값) : 힙에 값 추가
heapq.nlargest(n, 리스트) : 최댓값 n개
heapq.nsmallest(n, 리스트) : 최솟값 n개

코드

나의 코드

import heapq
def solution(scoville, k):
    answer = 0
    heap.heapify(scoville) # 기존 리스트 힙으로 변환
    while len(scoville) > 1:
        sc1 = heapq.heappop(scoville)
        sc2 = heapq.heappop(scoville)
        if sc1 < k and sc2 < k:
            heapq.heappush(scoville, sco1 + (sco2*2))
            answer += 1
        else:
            return answer
    if scoville[0]>= k:
        return answer
    else:
        return -1

이중우선순위큐

나의 풀이

스택과 힙을 사용하여 구현 가능 하다. 문제에서 제시한 대로 구현하면 된다.

코드

스택 사용 코드

def solution(operations):
    answer = []
    for i in operations:
        a, b = i.split(' ')
        if a == "I":
            answer.append(int(b))
        else:
            if len(answer) > 0:
                if b=='1':
                    answer.pop(answer.index(max(answer)))
                else:
                    answer.pop(answer.index(min(answer)))
            else:
                pass
    if not answer:
        return [0,0]
    else:
        return  [max(answer), min(answer)]

힙 사용 코드

import heapq
def solution2(operations):
    answer = []
    for i in operations:
        a,b = i.split(' ')
        if a== "I":
            heapq.heappush(answer, int(b))
        else : 
            if (len(answer)) == 0:
                pass
            elif b =='1':
                answer.pop(answer.index(heapq.nlargest(1, answer)[0])) # 최대값이 여러개라면 한개만 선택
            else:
                heapq.heappop(answer)
        
    if not answer:
        return [0,0]
    else:
         return [heapq.nlargest(1,answer )[0], heapq.nsmallest(1, answer)[0]]

디스크컨트롤러

나의 풀이

이 문제는 jobs 리스트를 소요 시간 기준으로 정렬하는 것이 아이디어가 포인트다.

스케줄링 알고리즘 중의 SJF(Shortest Job First) 는 가장 짧은 프로세스에게 cpu를 할당하는 기법인데, 이 아이디어를 이용하여 문제를 해결할 수 있다.

1. 소요 시간을 기준으로 정렬한다.
2. jobs를 다 체크할 때 까지 다음을 반복한다.
   • start는 시간인데, start보다 요청 시간이 작거나 같다면, start에는 소요시간을 더한다.
   • answer는 대기시간 + 소요시간이며, start(현재시간)-요청시간을 answer에 더하여, 순수 요청부터 종료까지 걸린 시간을 구한다.
   • 탐색한 작업은 pop한다.
   • 탐색할 작업이 마지막 작업이고, 마지막 작업의 요청시간이 현재시간(start)보다 크다면 시간을 1초씩 늘린다.

코드

나의 코드

def solution(jobs):
    answer = 0
    start = 0 # 현재까지 진행된 작업 시간
    length = len(jobs)
    # 소요 시간으로 정렬
    jobs = sorted(jobs, key=lambda x : x[1])
    while len(jobs)!=0:
        for i in range(len(jobs)):
            if jobs[i][0] <= start:
                start += jobs[i][1]
                answer += start - jobs[i][0]
                jobs.pop(i)
                break
            if i == len(jobs) -1:
                start +=1
    return answer // length