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

[git]
https://github.com/JungSangA/Algorithm_Study/blob/main/%EC%8A%A4%ED%83%9D%26%ED%81%90/%EB%8B%A4%EB%A6%AC%EB%A5%BC%20%EC%A7%80%EB%82%98%EB%8A%94%20%ED%8A%B8%EB%9F%AD.ipynb

1. while과 for문을 통한 단순 반복 아이디어

def solution(bridge_length, weight, truck_weights):
    answer = 0
    tmp_list = [0]*bridge_length
    idx = 0
    cnt = 1
    tmp_list[0] = truck_weights.pop(0)
    while True:
        if tmp_list.count(0) == len(tmp_list) and len(truck_weights) ==0:
            break
        
        for i in range(len(tmp_list)-1,-1,-1):
            if i == 0:
                tmp_list[i] = 0
            else:
                tmp_list[i] = tmp_list[i-1] 
        if len(truck_weights) !=0:
            if truck_weights[0]+sum(tmp_list) > weight:
                tmp_list[0] = 0
            elif truck_weights[0]+sum(tmp_list) <= weight:
                    tmp_list[0] = truck_weights.pop(0)
        cnt+=1
    return cnt

• while문 안에서 for문과 if문을 쓰며 idx도 수동 증가시키며 변수도 많이 생성하여 시간초과로 통과를 하지 못했다.

2. Queue를 통한 비교- sum(list) 내장함수 사용

def solution(bridge_length, weight, truck_weights):
    tmp_list = [0]*bridge_length
    cnt=0
    while True:
        # 탈출 조건
        if len(tmp_list)==0:
            break
        
        if len(truck_weights) !=0:
            tmp_list.pop(0)
            if truck_weights[0] + sum(tmp_list) > weight:
                tmp_list.append(0)
            else:
                tmp_list.append(truck_weights.pop(0))
        else:
            tmp_list.pop(0)
        cnt+=1

    return cnt

• 대부분 정답이 인정되었지만 3개가 시간초과가 뜨면서 통과를 하지 못했다.
• 시간 초과가 뜨는 이유는 정답이라고 볼 수 있는 알고리즘이지만 효율성이 떨어지는 상황이므로 시간을 절약할 수 있도록 효율성 있는 알고리즘을 짜는 방법을 생각해보아야 한다.

3. Queue를 통한 비교 - 변수를 통한 단순 덧셈&뺄셈

def solution(bridge_length, weight, truck_weights):
    tmp_list = [0]*bridge_length
    cnt=0
    bridge_sum = 0
    while True:
        # 탈출 조건
        if len(tmp_list)==0:
            break

        if len(truck_weights) !=0:
        	# 다리 위에 있는 트럭 중 앞에 있는 트럭의 무게 빼기
            bridge_sum -= tmp_list.pop(0) 
            # 다리 위에 새로운 트럭이 올라갔을 때 무게 중량 초과여부 판별
            if truck_weights[0] + bridge_sum > weight: 
                tmp_list.append(0)
            else:
     	        # 다리 위에 새로운 트럭이 올라갔으므로 트럭의 무게 추가
                bridge_sum += truck_weights[0] 
                tmp_list.append(truck_weights.pop(0))
        else:
            tmp_list.pop(0)
        # print (tmp_list)
        cnt+=1

    return cnt

• while문 안의 탈출 조건으로 다리위에 트럭이 없을 때 break를 걸어 while문을 빠져나간다.
• 대기중인 트럭이 있을 때 현재 다리위에 있는 트럭 열에서 먼저 쌓인 트럭 pop(0)으로 제거하면서 트럭의 무게를 단순 뺄셈으로 뺀다.
• 다리위에 있는 트럭과 대기중인 트럭의 무게를 합친 값과 다리가 버틸 수 있는 중량을 비교하여 다리에 올라갈 수 있을지 없을 지 판별한다.
• 다리에 트럭을 못올렸을 경우 시 0(무게=0, 트럭X)을 추가하여 한 turn이 지나갔음을 알려주고, 다리에 트럭을 올렸을 경우 truck_weight에서 pop(0)을 통해 값을 반환해주고, 그 값을 다리 위 리스트에 추가해준다.
• 남아있는 대기 트럭이 없을 경우 다리 위에 있는 트럭이 다 건널때까지 pop(0)을 통해 제거해준다.
• 이러한 일련의 과정이 1번씩 돌 때마다 cnt를 1씩 증가시켜 시간이 얼마나 걸리는지 판별하고 마지막에 cnt를 return 해준다.

내장함수의 편리함도 물론 중요하지만,
알고리즘 속에서 수식이 계속 반복된다면 단순한 수식을 직접 짜는게 알고리즘의 효율성면에서 더 좋을 수 있다!!!!