Skip to content

[Algorithm] 다리를 지나는 트럭 #102

@hwangJi-dev

Description

@hwangJi-dev

💬 문제

[코딩테스트 연습 - 다리를 지나는 트럭](https://school.programmers.co.kr/learn/courses/30/lessons/42583)


💬 Idea

  • 문제가 너무 불친절해서 이해하는데 시간이 걸렸다

  • queue의 원리를 이용하자

    🔑 
    1. queue의 첫번째 원소를 꺼내서 도착 트럭을 꺼낸다.
    
    - 트럭이 도착했다면
        - 다리 위의 트럭 개수 - 1
        - 다리 위의 트럭 무게 - 도착한 트럭 무게
    - 트럭이 도착하지 않은 경우에는 0이 꺼내짐
    
    2. 출발 대기중인 트럭 무게 + 현재 다리 위의 무게가 weight 이하이고
        출발 대기중인 트럭을 출발시켰을 때 다리 위의 트럭 개수가 기준 트럭 개수 이하라면 트럭을 출발시킨다
        - truck의 첫번째 원소를 다리 위에 올린다
        - 다리 위의 트럭 무게 + 출발한 트럭의 무게
        
    3. 매 반복마다 결과에 +1
    

💬 풀이

  • 매 반복마다 reduce함수를 써주니까 시간 초과가 발생해서 현재 다리 위에 올라간 트럭의 무게를 변수에 따로 저장해두어 해결했다.
func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {
    var truck = truck_weights
    var bridge: [Int] = Array(repeating: 0, count: bridge_length)
    var tc = (0,0)
    var ans = 0
    
    while !truck.isEmpty {
        let arrive = bridge.removeFirst()
        if arrive != 0 {
            tc.0 -= 1
            tc.1 -= arrive
        }
        
        if tc.1 + truck[0] <= weight && bridge_length >= tc.0 + 1 {
            let departure = truck.removeFirst()
            bridge.append(departure)
            tc.0 += 1
            tc.1 += departure
        } else {
            bridge.append(0)
        }
        
        ans += 1
    }
    
    return ans + bridge_length
}

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions