프로그래머스 - 다리를 지나는 트럭, 주식 가격, 더 맵게

 

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

코딩테스트 연습 - 다리를 지나는 트럭

 

class Truck :
    def __init__(self, weight):
        self.weight = weight
        self.time =0
        

def solution(bridge_length, weight, truck_weights):
    bridge = list()
    result_queue = []
    result_case_number = len(truck_weights)
    seconds = 0
    current_weight = 0
    while True:
        if bridge and bridge[0].time == bridge_length:
            out_truck = bridge.pop(0)
            result_queue.append( out_truck )
            current_weight -= out_truck.weight
        else :
            pass 
        if truck_weights and current_weight+ truck_weights[0]  <= weight:   
            enter_truck = Truck(truck_weights.pop(0))
            bridge.append(enter_truck)
            current_weight += enter_truck.weight
        else :
            pass
        for truck_bridge in bridge :
            truck_bridge.time += 1
        seconds += 1
        if len(result_queue) == result_case_number :
            break
        
    return seconds

다리에 올라와 있는 트럭은 bridge 리스트에 올려, 진행상태와 무게를 기록하기 위한 클래스 만들었고, 대기하는 트럭을 큐를 이용해 하나씩 빼가면서 진행시켰다

 

https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

 

def solution(prices):
    answer = [0] * len(prices)
    days= 0
    prices_history = list()
    for current_price in prices :
        while True :
            if prices_history and prices_history[-1][1] > current_price:
                out = prices_history.pop(-1)
                answer[out[0]] = days - out[0]
            else :
                prices_history.append([days , current_price])
                break
        days +=1
    days -=1
    for result in prices_history :
        answer[result[0]] = days - result[0]

    return answer

 

전체 주식 가격 배열을 For 문을 돌리면서, 스택에 현재 가격을 넣기전에 스택에 있는 값이 오늘보다 낮으면 pop 시키며 진행 시켰고,

 

빼낸 주식 가격들의 날짜 값을 비교하여 answer 배열에 넣었고,

 

while문이 끝나고도 남은 값은 days 계산하여 answer에 넣었다.

 

최대한 for문 한 번에 스택, 조건, 비교 까지 넣어서 진행하고자 하였다.

 

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

코딩테스트 연습 - 더 맵게

 

 

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville) > 1 : 
        min_1 = heapq.heappop(scoville)
        if min_1 >= K :
            return answer
        
        else :
            min_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, min_1+min_2*2)   
            answer += 1
    if heapq.heappop(scoville) >= K :
        return answer
    else :
        return -1

 

heap을 사용하여 쉽게 해결 할 수 있었다.

 

스코빌 지수를 python heapq 모듈을 활용하여 구현 하였다. 기본적으로 heapq 는 최소 heap으로 구현해주며

 

heapify(), heapq.heappush(), heapq.heappop() 3가지를 잘 쓰면 코테 문제 풀기에 좋을 거 같다

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

코딩테스트 연습 - 디스크 컨트롤러

 

import heapq  
def solution(jobs):
    jobs = sorted(jobs, key=lambda x: (x[0], x[1]))
    number = len(jobs)
    time = 0
    process_time = 0
    ready_queue = list()
    is_process = False
    answer = 0
    while jobs or ready_queue :
        while jobs and time == jobs[0][0]:
            ready_queue.append(jobs.pop(0)[1])
        ready_queue.sort()
        if process_time <= 0 :
            is_process = False
        else :
            is_process = True
        if  is_process :
            pass
        elif ready_queue  :
            process_time = ready_queue.pop(0)
            answer += process_time
        answer += len(ready_queue)
        time += 1
        process_time -=1 
    return int(answer/number)

 

시간복잡도 테스트가 중요한 문제였다.

 

두 가지 문제로 오래 걸렷는데

 

첫 번째는 같은 시간에 중복되서 올 것을 생각하지 못했다.'

 

두 번쨰는 당연히' 시간순서대로 올 것이라고 생각했고

 

첫 번째 문제는 빠르게 인지하여 코드를 고쳤지만, 두 번째 문제를 생각하지 못해서 코드를 이리저리 바꾸다 보니 

 

결론적으로는 큐로 해결했지만, 나중에 힙으로 구현하면 보다 코드도 짧고, 시간효율성도 좋게 풀 수 있을 거 같다.