알고리즘 - 프로그래머스 다리를 지나는 트럭

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

---

이번 문제도 언어처리에 대한 문제입니다.

 

문제의 요구사항은 아래와 같아요.

1. 1초에 1만큼 움직인다. (한칸?!)
2. 다리가 버틸 수 있는 무게 만큼만 차가 올라 갈 수 있다.
3. 다리의 길이가 n이라면 n초가 걸린다.

어렵게 생각할 필요없이 쉽게 기차놀이 하신다고 생각하면 될 것같아요.

 

위의 문제를 풀기위해서 저는 임의의 Struct를 가지는 Array배열을 선언해서 문제를 해결하겠습니다.

 

struct passingTruck {
    var endTime: Int
    var weight: Int
}

움직이는 차량이라는 Struct 구조체를 선언해주었구요. 변수로는 종료시간과 차량의 무게입니다.

 

문제를 해결하기 위해서는 For문 또는 While문을 실행해서 1식(1초)마다 프로세스를 연산하는 루프가 필요합니다.

 

반복문을 제어할 수 있는 변수들을 선언해줄게요.

var currentTime = 0 						  // 현재 진행 시간
var passingTruckArray = Array<passingTruck>() // 움직이고 있는 차량들의 배열
var passTruckCount = 0						  // 다리를 통과한 차량의 갯수
var passingLastIndex = 0					  // 마지막으로 다리에서 움직이는 차량 번호

 

그리고 아래처럼 반복문을 선언하고 조건에는 다리를 통과한 차량의 갯수가 솔루션에서 입력 받은 차량의 수보다 적을 경우에만

진행되게  선언하구요. 실행횟수(시간)을 1식 증가하도록 구성하였어요.

    while passTruckCount < truck_weights.count {
        currentTime += 1
    
		........
    }

 

그리고 이제 문제를 해결하기 위한 조건 2가지를 선언할 거에요.

2. 차량이 다리위의 전체 길이를 지나 갔는지 조건 -> 차량을 제거한다.
1. 차량이 다리위에 추가 될수 있는지 여부의 조건 -> 차량을 추가한다.

 

먼저 순환루프에서 현재 다리위에 있는 차량이 다 지나갔는지 여부에 대해서 확인하고

그 다음에 차량이 추가 될 수 있는지 확인하기 위한 조건을 추가 할 거에요.

// 차량이 다리위를 다 지나갔음을 파악하는 조건
if let truck = passingTruckArray.first, currentTime == truck.endTime {
	passingTruckArray.removeFirst()
	passTruckCount += 1
}

// 차량이 다리위에 추가 될 수 있는지 조건
if passingLastIndex < truck_weights.count {
	if passingTruckArray.map({ $0.weight }).reduce(0, +) + truck_weights[passingLastIndex] <= weight {
		 passingTruckArray.append(passingTruck(endTime: currentTime + bridge_length, weight: truck_weights[passingLastIndex]))
         passingLastIndex += 1
    }
}

 

먼저 차량이 다리를 다 지나 갈수 있는지에 대한 조건인데 차량의 배열에서 맨 앞 차량이 있다면

그 차량의 종료시간과 현재 시간을 비교하는 조건입니다.

if let truck = passingTruckArray.first, currentTime == truck.endTime {
	passingTruckArray.removeFirst()
    passTruckCount += 1
}

 

차량의 종료시간을 어떻게 알고, 그 시간으로 차량이 다리를 다지나가는것을 어떻게 확인하는가?

아래 예제의 코드 내용처럼 차량은 1초에 1칸식 움직일 수 있습니다. 그리고 다리의 길이는 고정되어 있조.

그렇다면 다리의 길이 만큼 실행 횟수가 진행되면 차량이 다 지나갔는지 여부를 알 수 있습니다.

차량 다리 통과 시간 = 현재 시간 + 다리의 길이

 

네 그리고 조건에 충족한다면 배열의 맨앞 차량을 제거하고, 통과한 차량의 갯수를 증가 시켜주면 됩니다.

 

왜 배열의 맨 첫번째만 파악하는가? 1초에 1칸식 밖에 움직이 못하는 1차선 도로입니다.

굳이 옆에 차량이 없기 때문에 뒷차량은 신경 쓰지 않아도 되는겁니다.

# 1초에 1칸식 밖에 움직이는 전제 조건이 있습니다.

struct passingTruck {
    var endTime: Int
    var weight: Int
}

다리길이 -> bridge_length = 5
현재 시간 -> currentTime = 1

var truck = passingTruck(endTime: currentTime + bridge_length, weight: 10) 
// currentTime(1) + bridge_length(5) = 6
while true {

    if truck.endTime == currentTime {
	    break
    }
 
	currentTime += 1
}

 

 

그리고 차량이 추가 되는 조건을 선언 할게요.

if passingLastIndex < truck_weights.count {
	if passingTruckArray.map({ $0.weight }).reduce(0, +) + truck_weights[passingLastIndex] <= weight {
		passingTruckArray.append(passingTruck(endTime: currentTime + bridge_length, weight: truck_weights[passingLastIndex]))
		passingLastIndex += 1
	}
}

 

추가되는 조건 또한 간단합니다.

 

마지막으로 다리위에 추가되는 차량의 인덱스 번호가 총 통과해야할 차량의 갯수보다 작을 경우 조건문에 들어옵니다.

그리고 이제 다리위에 차량이 올라 갈 수 있는지 중량에 대한 조건을 확인하여야 합니다.

passingTruckArray.map({ $0.weight }).reduce(0, +) + truck_weights[passingLastIndex] <= weight

차량배열의 각 차량에 대한 중량에 대해서 reduce함수를 사용하여 모두 더해준뒤에 다리위의 마지막 차량의 다음차량의 무게를 더해줘서

이 무게가 다리가 하중 할수 있는 무게를 넘지 않으면 차량을 추가해 줄겁니다.

 

차량을 추가해줄때는 이 차량이 언제 다리위를 지날 수 있는지 시간을 추가해주면 됩니다.

그리고 다음에 올라올 차량에 대한 인덱스 번호를 1 증가 시켜주면 됩니다.

# 차량의 종료시간은 위에 설명해드렸조? 

   - 종료시간 : 현재시간 + 다리위의 길이

passingTruckArray.append(passingTruck(endTime: currentTime + bridge_length, weight: truck_weights[passingLastIndex]))
passingLastIndex += 1

 

이렇게 되면 모든 연산이 종료되고 문제는 해결됩니다.

 

단. 이렇게 하면 불필요한 연산이 생길수 있습니다. 

예를 들어 다리길이가 10000이고 다리가 무게를 버틸수 있는 중량 1이고, 차량의 배열을 [1,1,1,1,1] 이렇게 입력된다면,

차량은 1대식 밖에 못올라가고 while문은 불필요한 10000번의 연산을 진행하게 될겁니다.

 

그렇기 때문에 차량이 다리위에 올라 갈 수 있는지 중량 여부를  체크할때 else문을 추가 하여 불필요한 연산을 줄여줄겁니다.

if passingLastIndex < truck_weights.count {
	if 다리가 버틸수 있는 중량 <= 다리위의 총 중량 + 다음 차량의 중량 {
    	.....
    } else {
		currentTime += passingTruckArray.first != nil ? passingTruckArray.first!.endTime - currentTime - 1 : 0
	}
}

1초에 한칸식 이기 때문에 현재 다리위의 맨 앞차량이 몇초간 더 다리위를 지나는 연산을 해야하는지 여부를 파악 할 수 있습니다.

그러기 위해서는 아래와 같이 계산하면 몇초가 지난 후에 맨 앞차량이 다리위를 지나는지 시간이 나오게 됩니다.

 

맨앞차량이 다리를 지나가기 까지 필요한 시간 = 맨앞차량의 종료시간 - 현재시간 - 1초 

(-1초를 하는 이유는 while문 진행시 초기에 1초식 증가해주기 떄문입니다.)

 

그 나온값을 현재시간에 더해준다면 불필요한 연산이 생략이 되겠조?.

 

 

전체 코드입니다.

import Foundation

struct passingTruck {
    var endTime: Int
    var weight: Int
}

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var currentTime = 0
    var passingTruckArray = Array<passingTruck>()
    var passTruckCount = 0
    var passingLastIndex = 0
    
    while passTruckCount < truck_weights.count {
        currentTime += 1
    
        if let truck = passingTruckArray.first, currentTime == truck.endTime {
            passingTruckArray.removeFirst()
            passTruckCount += 1
        }
        
        if passingLastIndex < truck_weights.count {
            if passingTruckArray.map({ $0.weight }).reduce(0, +) + truck_weights[passingLastIndex] <= weight {
                passingTruckArray.append(passingTruck(endTime: currentTime + bridge_length, weight: truck_weights[passingLastIndex]))
                passingLastIndex += 1
            } else {
                currentTime += passingTruckArray.first != nil ? passingTruckArray.first!.endTime - currentTime - 1 : 0
            }
        }
    }
    
    return currentTime
}

print("result Time = \(solution(100, 100, [10,10,10,10,10,10,10,10,10,10]))")

 

 

맨 마지막 조건을 추가한것과 아닌것에 대한 프로세스 연산 속도 비교입니다. (프로그래머스 사이트 내의 연산 속도)

테스트 4번, 5번, 6번 등과 같이 심하게는 100배 이상 시간 차이가 나는 것을 볼 수 있습니다.

 

# 조건 미추가시

# 조건 추가시

 

 

(사진... 한줄에 두개 어떻게 추가하나요..? ㅠㅠ)