[알고리즘] 2024.09.29 풀이

풀이 사이트: 프로그래머스 고득점 Kit! 

# 완전 탐색

📝 모음 사전 (lv 2) - https://school.programmers.co.kr/learn/courses/30/lessons/84512

* 체감 난이도 : ⭐️ - - - -

- 이건 그냥 수학 문제라 기록할 것도 없다.
- 완탐까지 갈 필요도 없이 그냥 경우의 수만 따지면 되는 의미 없는 문제라고 생각한다.

def solution(word):
    answer = 0
    dic = {"A":0, "E":1, "I":2, "O":3, "U":4}
    for i in range(len(word)):
        for j in range(5-i):
            answer += dic[word[i]] * 5 ** (j)
    return answer + len(word)

 

 

# 우선순위 큐

📝 디스크 컨트롤러 (lv 3) - https://school.programmers.co.kr/learn/courses/30/lessons/42627

* 체감 난이도 : 💀💀💀💀💀

- 아 풀다가 답답해서 반례 봐버렸다... 못 푼걸로 치도록 하겠다.
- 아이디어는 단순하게 가장 소요시간이 적은 작업을 가능한 빨리 시작하는 것이였다.
- 문제 제한이 최대 1000이 걸리는 작업 최대 500개가 제한이였기 때문에 500000 크기의 배열을 만들어 시작 시간 순서 상관 없이 작업이 언제 시작해서 언제 끝났는지를 저장하고자 했다.
- 이를 위해선 각 작업의 시작 가능한 시간을 찾고 해당 시간부터 소요 시간동안 어떠한 작업도 이루어지지 않았는지 확인을 해야했기 때문에 각 작업당 n^2의 시간이 걸리게 된다. (n개의 작업시 n^3)
- 그래서 다음 생각한 아이디어가 시간의 순서를 적용시키는 것이였다.
- 시간의 흐름상 앞에서부터 작업을 진행시킨다.
- 이때 최소의 작업 대기시간을 만들기 위해서 핵심 아이디어가 필요하다.
- '바로 시작가능한 밀린 작업 중 가장 소요시간이 짧은 작업'이다.
- 매 순간 짧은 작업은 선택 해야하는 이유는 예제에서도 드러나듯, 선행하는 작업의 소요시간이 그 시간에 시작 가능한 모든 작업에 적용되기 때문에 가장 짧은 작업부터 선택해야 오버헤드가 최소화 된다. 
- 그 뿐만 아니라, 작업을 하지 않는 시간을 없애는 것도 중요하다.
- 시작 시간에 상관없이 가장 소요시간이 짧은 것부터 선택했을 때 해당 작업이 현재 시간 이후에 시작 가능하면 그 사이 시간동안 어떠한 작업도 할 수 없다면 당연히 평균 대기시간이 늘어나게 될 것이다. (이러한 점에서 첫 번째 방법은 아예 잘못됐다고 볼 수 있다)
- 위의 조건을 모두 만족시키기 위해 작업들을 시작 시간 순으로 정렬하고, 짧은 소요시간을 우선으로하는 우선순위 큐를 사용하였다.
- 방식은 다음과 같다.
   1-1. 모든 작업을 완료할 때까지, 현재 바로 시작가능한 작업들을 우선순위 큐에 집어넣는다.
   1-2. 만약 현재 시작 가능한 작업이 없을 경우 가장 빨리 시작 가능한 작업을 기준으로 현재시간을 조정한다.
   2. 우선순위 큐 가장 첫 요소가 바로 위에서 말한 현재 시작 가능한 작업 중 소요시간이 가장 짧은 작업에 해당하기 때문에 빼내어 대기시간(현재시간 + 소요시간 - 시작가능 시간)을 저장하고 현재시간을 소요시간만큼 늘린다.
   3. 모든 대기시간을 더한 값에서 총 작업 개수를 나눠 평균 대기시간을 구한다.
- 반례를 본 이유가 1-2 때문이다.
- 첫번째 아이디어에서 두번째 아이디어로 코드를 변경할 때 뇌리에 남아있던 저 부분을 망각해버려서 작업이 절대 있을 수 없는 빈 시간이 생길 경우 더 이상 진행을 하지 않았다. (예제는 그런 일이 없어서 빼먹은걸 반례 보기 전까지 알 수가 없었다)

import heapq

def solution(jobs):
    answer = 0
    
    heap = []
    original = []
    
    for i in range(len(jobs)):
        heapq.heappush(original, (jobs[i][0], jobs[i][1]))
        
    current_time = original[0][0] + original[0][1]
    answer = current_time - original[0][0]
    heapq.heappop(original)
    while True:
        while len(original) != 0 and original[0][0] <= current_time :
            temp = heapq.heappop(original)
            heapq.heappush(heap, (temp[1], temp[0]))
            
        if len(heap) == 0:
            if len(original) == 0:
                break
            current_time = original[0][0]
            temp = heapq.heappop(original)
            heapq.heappush(heap, (temp[1], temp[0]))
            continue
            
        temp = heapq.heappop(heap)
        current_time += temp[0]
        answer += current_time - temp[1]

    answer //= len(jobs)
    return answer