[프로그래머스] 스택/큐 다리를 지나가는 트럭 (python)

1차 시도

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    print(truck_weights)
    # 줄줄이 도착하는 경우 (모든 트럭 무게 <= weight)
    min_time=(bridge_length+1)+(len(truck_weights)-1)
    answer = min_time
    
    for i in range(0,len(truck_weights)-1) :
        # 2개씩 무게 비교 들어가자
        if truck_weights[i]+truck_weights[i+1] > weight:
            answer += (bridge_length -1)

    
    return answer

아이디어

• 최소시간(min_time)에서 지연 시간을 더해서 결과값을 구하자는 생각이었습니다. (괜찮은 아이디어일 것 같은데)
• 최소시간은 트럭이 다리에 줄줄이 들어올 수 있어서 줄줄이 다리를 빠져나가는 경우입니다.
• 모든 트럭 무게의 합이 weigth보다 작거나 같으면 가능한 경우이죠.
• 지연 시간은 truck_weights에서 2개씩 트럭 무게를 더했을 때 weight를 넘는 경우에 발생을 한다고 생각했었습니다.

놓친 부분 (틀린 이유)

• 지연 시간을 고려할 때, 2개씩의 트럭만 고려했기 때문에 틀렸습니다.
• 다리에 진입한 트럭이 경우에 따라 3개, 4개 ... 가 될 수 있기 때문입니다.
• 다리에 진입한 트럭이 2개라고만 생각해서 지연시간을 구했으니 당연히 틀린 코드였습니다.

 

 

2차 시도

def solution(bridge_length, weight, truck_weights):
    

    length=len(truck_weights)
    
    # 첫번째 트럭은 무조건 1초에 들어옴
    bridge=[truck_weights[0]]
    cnt=[1]
    answer=1
    
    #2초부터는
    while True :
        answer += 1
        # 다리 지난 트럭은 bridge에서 나가야 되는데 (길이만큼의 time 동안 머물러 있었다면 나가야됨)
        if cnt[0] == bridge_length :
            bridge.pop(0) 
            cnt.pop(0)
        
       
        if len(truck_weights) != 0 :
             # 다리에 진입함
            if sum(bridge) + truck_weights[0] <= weight:
                bridge.append(truck_weights.pop(0))
                cnt.append(1)
        for i in range(len(cnt)-1):
            cnt[i] += 1 
                    
        # 모든 트럭이 다리를 지나감    
        if len(bridge) == 0:
            break

    
    return answer

아이디어

• 다리에 진입하는 트럭을 bridge 리스트에 넣습니다.
• truck_weights에 첫번째 트럭을 pop 해서 bridge 리스트에 append 하는 것입니다.
• 단, bridge안에 있는 트럭들의 무게 합과 truck_weights에 첫번째 트럭의 합이 weight보다 크지 않아야 하겠죠.
• 또한, bridge 리스트에 트럭이 얼마만큼 머물렀는지에 대한 시간을 cnt 리스트에 저장합니다.
• 언제 bridge를 빠져나갈지 판단해야 되기 때문입니다. (bridge_length 만큼 머물렀다면 다리를 빠져나가게 됩니다.)

놓친 부분 (틀린 이유)

• 왜 틀렸을까요..? 실행시간 초과가 뜹니다 ㅠㅠ

 

다른 분의 풀이 

def solution(bridge_length, weight, truck_weights):
    time = 1 
    passing_truck= []
    passed_truck= []
    current_mass = 0
    # **딕셔너리 자료형
    time_dic = {}

    while True:
        while truck_weights:
            if weight >= current_mass + truck_weights[0]:
                passing_truck.append(truck_weights.pop(0))
                # ***** time초에 들어온 트럭은 time+bridge_length 후에 나간다.
                time_dic[time] = bridge_length + time 
                current_mass = sum(passing_truck)
                # while truck_weights 문을 빠져나감
                break  
            else :
                break
        
        time += 1

        # 나갈 타이밍이 됐는지 확인
        for out_time in time_dic:
            if time_dic[out_time] == time:
                passed_truck.append(passing_truck.pop(0))

        current_mass = sum(passing_truck)

        # 모든 트럭이 passed_truck으로 넘어갔을 때
        if passing_truck == [] and truck_weights== []:
            break
    return time

아이디어

• 딕셔너리 자료형을 사용합니다. key에는 time, value에는 time초에 들어온 트럭이 나가는 시간을 저장합니다.

 

 

python 개념

1) while문 조건에 배열이름만 적는 경우

while truck_weights:

truck_weigths에 값이 있으면 True, 없으면 False

2) 딕셔너리 자료형 (Hash)

순차적으로 값을 구하지 않고, key를 통해 value를 구합니다. key는 변하지 않는 값입니다. 그래서 리스트나 딕셔너리가 key가 될 수는 없습니다. value에는 아무거나 집어넣을 수 있습니다.

a = {1: 'a'}
a[2] = 'b'
print(a)
# {1: 'a', 2: 'b'}
del a[1]
print(a)
# {2:'b'}

key가 중복되면 맨 마지막 값을 제외한 나머지들은 무시됩니다.

a={1:'hihi', 1:'sunny',1:'bye'}
print(a[1])
# bye

딕셔너리 자료형을 리스트로 만들 수 있습니다.

dic={1:'hihi',2:'sunny',3:'bye'}

list(dic.keys())
#[1,2,3]
list(dic.values())
#['hihi','sunny','bye']
list(dic.items())
#[(1,'hihi'),(2,'sunny'),(3,'bye')]