코딩테스트/프로그래머스

[프로그래머스] 다리를 지나는 트럭 (Swift)

도지대디 2022. 5. 21. 01:10

[프로그래머스] 다리를 지나는 트럭 (Swift)

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

 

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

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈

programmers.co.kr

풀이

1. 다리

현재 다리 위에 어떤 트럭들이 올라가 있는지에 대한 정보를 저장할 수 있는 자료구조가 필요했습니다.

 

먼저 다리를 건너기 시작한 트럭이 먼저 다리를 다 건너기 때문에 큐를 활용할까 생각했지만, 각 트럭이 다리에 머물러 있는 시간을 세는 방식이 애매하다고 생각하였습니다.

 

다리의 길이만큼 배열을 선언하기로 하였습니다. 배열의 모든 원소를 0 으로 초기화시켜 트럭을 삽입한 후 인덱스를 한 칸씩 옮겨주게 되면 다리를 건너는 모양새를 만들 수 있었습니다.

길이가 5 인 다리를 무게가 1 인 트럭이 건너는 모습
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 1, 0, 0, 0]
[1, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

2. 무게

다리는 버틸 수 있는 최대 무게가 정해져있기 때문에 현재 다리에 올라가있는 트럭들의 무게 합과 다음에 다리에 올라갈 트럭의 무게 합이 최대 무게보다 작거나 같아야 했습니다.

 

이전에 파이썬으로 문제를 풀이할 때는 sum() 함수를 이용하여 이를 처리하였는데, 이는 O(n) 만큼의 시간이 소요되기 때문에 더 효율적인 방법이 필요했습니다.

 

그래서 다리의 무게를 담아주는 변수를 선언하고 계속해서 값을 업데이트 시켜주었습니다. 다리에 트럭이 올라간다면 변수에 트럭의 무게를 더해주고, 트럭이 다리를 다 건널 때에는 변수에서 해당 트럭의 무게를 빼주었습니다.

 

위와 같은 방법으로 문제를 해결할 수 있었습니다.

코드