방구석프로의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/42627

문제 해결을 위한 과정

이 문제의 경우 heapq를 이용하면 해결할 수 있는 문제였습니다.

과정을 설명하면 다음과 같습니다.

1. jobs 리스트 정렬

2. 맨 처음 인덱스에 해당하는 값을 이용해 finish, answer 할당(finish는 작업이 끝나는 시간, answer는 대기 시간)

3. 다시 jobs 리스트를 정렬하며 finish 보다 request가 이전인 경우(작업 중에 들어온 요청인 경우) heapq에 삽입

4. heapq가 존재하면 가장 짧은 duration을 가진 작업을 이용해서 finish, answer 재할당

5. heapq가 존재하지 않으면 jobs리스트를 정렬하며 맨 처음 인덱스에 해당하는 값을 이용해 finish, answer 할당

이 부분에서 8번 18번 테스트 케이스를 틀렸었는데 이는 동일 request에 여러 작업이 들어올 수 있기 때문입니다. 따라서 jobs 리스트를 정렬 시 lambda를 이용해서 request기준으로 오름차순을 하고, 만약 request가 같다면 duration으로도 오름차순 정렬을 해주면 됩니다.

소스코드

import heapq

def solution(jobs):
    answer = 0
    length = len(jobs)
    length2 = len(jobs)
    jobs.sort(key = lambda x: (x[0], x[1]))
    finish = 0
    finish = jobs[0][1] + jobs[0][0]
    answer += jobs[0][1]
    jobs.pop(0)
    length2 -= 1
    
    while length2 != 0:
        jobs.sort(key = lambda x: (x[0], x[1])) 
        q = []
        for i in range(len(jobs)):
            request, time = jobs[i]
            if request <= finish:
                heapq.heappush(q, (time, request, i))
        if len(q) != 0:
            time, request, idx = heapq.heappop(q)
            if request <= finish: # 하드디스크 작업 수행 중 들어온 요청인 경우
                finish = finish + time
                answer += finish - request
                length2 -= 1
                jobs.pop(idx)
            else:
                heapq.heappush(q, (time, request, idx)) # 하드디스크가 작업 수행을 하지 않는 경우   
        else:
            jobs.sort(key = lambda x: (x[0], x[1])) 
            request, time = jobs[0] # 가장 앞에 작업 수행
            finish = request + time
            answer += finish - request
            jobs.pop(0)
            length2 -= 1
    answer = answer // length
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 해결을 위한 과정

이 문제의 경우 deque를 이용하면 쉽게 해결할 수 있는 문제였습니다.

과정은 다음과 같습니다.

1. 다리에 존재하는 트럭들 한 칸 이동시키기 - queue를 (truck, cnt)로 pair 형태로 넣어두면 cnt를 1 증가시키는 걸로 가능

2. 1의 과정 이 후 제일 앞에 있는 트럭의 cnt가 bridge_length와 같다면 popleft 해주기. (다리를 다 이동한 경우)

3. 다리에 존재하는 트럭들의 무게를 확인하여 남은 트럭 중 제일 앞에 트럭을 올려도 올라가는지 확인

    3-1. 올라갈 수 있다면 다리에 올리기

    3-2. 올라갈 수 없다면 다리에 올리지 않기

소스코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    finish = deque()
    moving = deque()
    length = len(truck_weights)
    
    while True:
        if len(finish) == length:
            break
        answer += 1
        for i in range(len(moving)): # 이동
            truck, cnt = moving[i]
            moving[i] = truck, cnt + 1           
        if len(moving) != 0:
            truck, cnt = moving[0] 
            if cnt == bridge_length: # 다리 다 이동하면 finish로 이동
                finish.append(moving.popleft())
        tempWeight = 0
        for i in range(len(moving)):
            truck, cnt = moving[i]
            tempWeight += truck
        if len(truck_weights) != 0 and tempWeight + truck_weights[0] <= weight:
            moving.append((truck_weights[0], 0))
            truck_weights.pop(0)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42586

문제해결을 위한 과정

이 문제는 각 배열을 조회하면서 해당하는 speeds를 더해주면 됩니다. 그 후 100이 넘는지 확인한 뒤(작업 완료) 완료된 작업만큼을 꺼내주면 되는 문제입니다. 단 이때 해당하는 인덱스의 speeds도 꺼내줘야 합니다. 소스코드는 다음과 같습니다.

소스코드

def solution(progresses, speeds):
    answer = []
    while True:
        if len(progresses) == 0:
            break
        for i in range(len(progresses)):
            progresses[i] += speeds[i]
        cnt = 0
        for i in range(len(progresses)):
            if progresses[i] >= 100:
                cnt += 1
            else:
                break
        for i in range(cnt):
            progresses.pop(0)
            speeds.pop(0)
        if cnt > 0:
            answer.append(cnt)
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12906

문제 해결을 위한 과정

이 문제는 배열의 길이 1,000,000 이므로 이중 For문이 아닌 단일 for문으로 해결해야 합니다.
현재 인덱스와 다음 인덱스를 비교해서 다른 경우에만 answer 리스트에 append 해주는 식으로 쉽게 해결할 수 있습니다.

소스코드

def solution(arr):
    answer = []
    arr.append("a")
    for i in range(len(arr)-1):
        if arr[i] != arr[i+1]:
            answer.append(arr[i])
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 해결을 위한 과정

이 문제는 heapq를 이용하면 쉽게 해결할 수 있는 문제였습니다. 매번 정렬을 한다면 효율성의 문제가 생길 수 있으므로 최소힙을 이용해 O(logN)으로 가장 작은 값을 꺼내면 됩니다. 이 때 2개씩 꺼내어 더 맵게 하는 과정을 거치는데 q의 길이가 1이라면 두번을 꺼낼 수 없으므로 예외처리를 따로 해주시면 됩니다.

소스코드

import heapq

def solution(scoville, K):
    answer = 0
    q = []
    for i in range(len(scoville)):
        heapq.heappush(q, scoville[i])
    while True: 
        if len(q) >= 2:
            num1 = heapq.heappop(q)
            num2 = heapq.heappop(q)
        elif len(q) == 1:
            num1 = heapq.heappop(q)
            if num1 < K:
                answer = -1
                break
        if num1 >= K:
            break
        answer += 1
        heapq.heappush(q, (num1 + num2 * 2))
    
    return answer