프로그래머스 Study 2주차

더 맵게 - 힙(Heap), Level2

import heapq

def solution(scoville, K):
        
    answer, count = -1, 0
    heapq.heapify(scoville) # scoville 리스트를 heap 자료구조로 만듬
    
    while True:
        if scoville[0] >= K: # heap은 가장 앞 value가 우선순위를 가짐 (= 가장 작음)
            answer = count
            break
        if len(scoville) < 2: # 새로운 스코빌 지수를 구하지 못하는 경우
            break

        first_value = heapq.heappop(scoville)
        second_value = heapq.heappop(scoville)
        new_value = first_value + second_value * 2
        heapq.heappush(scoville, new_value)
        
        count += 1

    return answer

1. heapq를 활용해 우선순위 큐로 만든다. (우선순위: 스코빌지수 ASC)

2. 새로운 스코빌 지수를 생성하고 우선순위큐에 삽입하는 동작을 반복한다.

3. 적절한 조건들을 섞는다.

    3.1.) 모든 음식의 스코빌 지수가 K 이상인 경우 → 가장 우선순위가 높은 (= 가장 스코빌 지수가 낮은) 값이 K 이상인 경우

    3.1.) 새로운 스코빌 지수를 구하지 못하는 경우

 

 

디스크 컨트롤러 - 힙(Heap), Level3

import heapq
from collections import deque

def solution(jobs):
    
    jobs.sort()
    jobs = deque(jobs)
    n, waits, process, occupy = len(jobs), [], None, False # 작업개수, 대기작업 리스트, 진행작업, 점유여부
    answer, count = 0, 0
    
    while jobs or waits or process: # 작업, 대기작업, 진행작업 하나라도 있는 경우
        
        while jobs: # 작업 시작시간이 된다면 대기작업으로 이동
            if jobs[0][0] == count:
                start, length = jobs.popleft()
                heapq.heappush(waits, [length, start, 0]) # [점유예정시간, 시작시간, 점유시간]
            else:
                break
    
        if not occupy and waits: # 진행작업이 없으면서 대기작업이 있는 경우
            occupy = True
            process = heapq.heappop(waits)
        
        if occupy:
            process[2] += 1 # 점유시간++
            if process[0] == process[2]: # 작업완료 (점유시간이 점유예정시간을 채운 경우)
                answer += count + 1 - process[1] # (종료시간 - 시작시간)
                occupy = False
                process = None
        
        count += 1
    
    return answer // n

1. 작업 리스트, 대기작업 리스트, 진행작업으로 분리한다.

    1.1.) 작업 리스트 (jobs): 큐로 구현했고 시작시간을 기준으로 정렬했다. 현재시간이 시작시간이 되면 대기작업 리스트로 이동한다.

    1.2.) 대기작업 리스트 (waits): heapq를 활용해 우선순위큐로 구현했다. (우선순위: 점유예정시간 ASC)

    1.3.) 진행작업 (process): 디스크가 점유하지 않을 때 우선순위가 가장 높은 대기작업을 진행한다.

2. 작업 리스트, 대기작업 리스트, 진행작업 모두 없는 경우까지 각자의 역할을 다하는 동작을 반복한다.

    2.1.) 작업 리스트의 작업이 시작시간이 된다면 대기작업 리스트로 이동

    2.2.) 디스크가 점유하지 않고 대기작업 리스트에 작업이 있는 경우 우선순위가 가장 높은 작업을 진행작업으로 이동

    2.3.) 진행작업이 완료될 때 (종료시간 - 시작시간)을 기록

 

 

이중우선순위큐 - 힙(Heap), Level3

import heapq

def solution(operations):
    
    lower_heap, higher_heap, answer = [], [], [0, 0] # 최소우선순위 큐, 최대우선순위 큐, 정답
    
    for operation in operations:
        opcode, number = operation.split(' ')
        number = int(number)
        
        if opcode == 'I': # I: 두 큐 모두에 값 삽입
            heapq.heappush(lower_heap, number)
            heapq.heappush(higher_heap, -number)
        
        elif opcode == 'D' and number == -1 and lower_heap: # D -1
            val = heapq.heappop(lower_heap) # 최소우선순위 큐 POP
            if higher_heap and -higher_heap[0] < val: # 최소우선순위 큐, 최대 우선순위 큐 값 역전 → 초기화
                lower_heap, higher_heap = [], []
            elif higher_heap and -higher_heap[0] == val: # 최소값과 최대값이 같다면
                heapq.heappop(higher_heap)
                if higher_heap and -higher_heap[0] == val: # 1. 같은 값이 중복되어 여러개인 경우 → pass
                    pass
                else: # 2. 같은 값이 하나인 경우 → 초기화
                    lower_heap, higher_heap = [], []
        
        elif opcode == 'D' and number == 1 and higher_heap:
            val = -heapq.heappop(higher_heap) # 최대우선순위 큐 POP
            if lower_heap and lower_heap[0] > val: # 최소우선순위 큐, 최대 우선순위 큐 값 역전 → 초기화
                lower_heap, higher_heap = [], []
            elif lower_heap and lower_heap[0] == val:
                heapq.heappop(lower_heap)
                if lower_heap and lower_heap[0] == val: # 1. 같은 값이 중복되어 여러개인 경우 → pass
                    pass
                else: # 2. 같은 값이 하나인 경우 → 초기화
                    lower_heap, higher_heap = [], []
        
    if lower_heap:
        answer[1] = lower_heap[0]
    if higher_heap:
        answer[0] = -higher_heap[0]
    return answer

1. 최소우선순위 큐, 최대우선순위 큐 2가지를 구현한다.

2. 각 우선순위 큐를 기준으로 최소값, 최대값을 POP한다.

3. POP한 값이 반대 우선순위 큐의 가장 높은 우선순위 값과 하나만 같거나 역전되는 경우 초기화한다.

    3.1.) 같은 값이 2개로 중복되는 경우가 있을 수 있으므로 조건을 추가해 이를 방지한다.

 

 

가장 큰 수 - 정렬, Level2

def solution(numbers):
    
    str_numbers = list(map(str, numbers))
    str_numbers.sort(key = lambda x: x * 3, reverse = True)
    answer = ''.join(str_numbers)
    
    if answer.startswith('0'):
        return '0' # '0' * (n) 인 경우: '0'
    return answer

1. numbers를 문자열로 변경한다.

2. 각 원소 * 3을 기준으로 정렬(DESC)한다.

    ex.) '81', '8', '813' -(*3)→ '818181', '888', '813813813' -(sort DESC)→ '888', '818181', '813813813' -(result)→ '881813'

 

 

H-Index - 정렬, Level2

def solution(citations):
    
    answer = 0
    
    while True:
        count = 0 # answer 이상으로 인용된 논문 수
        for citation in citations:
            if citation >= answer:
                count += 1

        if count < answer: # h번 이상 인용된 논문이 h편 이상이 아닌 경우
            break
        
        answer += 1

    return answer - 1

※ 정렬을 사용하지 않고 구현으로 풀었다.

1. H-Index가 될 수 있는 경우를 구한다.

2. 경우들 중 (H-Index가 될 수 없는 경우의 최소값) - 1가 정답이다.

 

 

체육복 - 탐욕법(Greedy), Level1

def solution(n, lost, reserve):
    
    answer, clothes = 0, [1] * n # 정답, 체육복 개수 리스트
    for idx in lost: clothes[idx - 1] -= 1
    for idx in reserve: clothes[idx - 1] += 1
    
    for i in range(len(clothes)):
        if clothes[i] == 0: # 체육복이 없는 경우
            if i > 0 and clothes[i - 1] == 2: # 좌측 체육복 2개인 경우 (좌측부터 이동하기 때문에 좌측 우선 확인)
                clothes[i] += 1
                clothes[i - 1] -= 1
            elif i < len(clothes) - 1 and clothes[i + 1] == 2: # 우측이 체육복 2개인 경우
                clothes[i] += 1
                clothes[i + 1] -= 1
    
    for cloth in clothes:
        if cloth > 0:
            answer += 1
    return answer

1. (idx - 1)번의 학생이 가지고 있는 체육복 개수 리스트를 만든다.

2. 체육복이 없는 학생을 기준으로 체육복이 남는 학생의 체육복을 가져온다.

    2.1.) 좌측에서 우측으로 이동하기 때문에 좌측을 먼저 확인해야 한다.

 

 

입국심사 - 이분탐색, Level3

def binary_search(low, high, n, times, answer):
    
    if low > high: # 분기 조건
        if answer == None: # 만약 answer를 구하지 못한 경우
            return low # mid가 조건을 만족한 적이 없음을 의미 → 즉 조건을 만족한 값은 끝값인 low
        return answer
    
    mid = (low + high) // 2
    
    count = 0
    for time in times:
        count += (mid // time)
    
    if count >= n:
        if count == n:
            answer = mid # 계속 작아지는 방향으로 이동하기 때문에 mid를 answer로 계속 저장
        return binary_search(low, mid - 1, n, times, answer)
    elif count < n:
        return binary_search(mid + 1, high, n, times, answer)
    

def solution(n, times):

    result = binary_search(min(times), max(times) * n, n, times, None)
    return result

1. 심사를 받는 시간을 기준으로 이분탐색을 진행한다.

2. 이분탐색을 진행하는 조건은 이분탐색 기준인 시간 동안 몇 명의 사람이 심사받을 수 있는지 이다.

3. 다른 이분탐색과 분기조건은 같다.

    3.1.) 그러나 정답을 구하지 못한 상태로 계속 좌측으로 이동한 경우 끝값(low)이 정답이고 우측의 값은 정답을 만족하지 못한 경우이다.

 

 

징검다리 - 이분탐색, Level4

1. 아직 역량이 부족하다.