제이슨의 개발이야기
[프로그래머스] 다리를 지나는 트럭 level 2 코틀린 본문
https://programmers.co.kr/learn/courses/30/lessons/42583
코딩테스트 연습 - 다리를 지나는 트럭
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈
programmers.co.kr
안녕하세요 일요일 주말에 저는 프로그래머스 에서 다리를 지나는 트럭 이란 문제를 풀었습니다
제가 프로그래머스 에서 주로 레벨 1 부터 시작하다가 요 근래 레벨 2 로 올라가서 문제를 풀고있는대 여전히 저에게는 어려운거같습니다 ㅠㅠ 이 문제 푸는대 2틀정도... 걸린거 같고 그것도 모자라서 결국 구글 서칭을 통해 힌트를 얻어서 문제를 풀었습니다..
힌트를 보고 문제를 풀다보니 제 코드와 다른 사람의 코드가 굉장히 유사해지더라구요.. 그래서 개인적으로 따로 공부하는 시간을 갖었습니다!
요번에는 코틀린으로 문제를 풀어봤습니다!
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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_length | weight | truck_weights | return |
2 | 10 | [7,4,5,6] | 8 |
100 | 100 | [10] | 101 |
100 | 100 | [10,10,10,10,10,10,10,10,10,10] | 110 |
제가 힌트로 얻은 것은 다리를 지나는 트럭의 큐와 대기하는 트럭 큐를 만들고
다리를 지나는 트럭에 순서에 맞게 데이터를 넣대 조건에 부합하지 않은경우(지나고 있는 트럭들 + 대기하는 트럭 중 첫번째 값이 weigths보다 클 경우) 0을 넣어서 뒤에 트럭이 없다 라는 것을 표시하는 것이 였습니다 !
import java.util.*
class Solution {
fun solution(bridge_length: Int, weight: Int, truck_weights: IntArray): Int {
var answer = 0
var bridgeQueue = LinkedList<Int>()
var waitQueue = LinkedList<Int>()
for(i in 0 until bridge_length) bridgeQueue.add(0)
for(i in truck_weights.indices) waitQueue.add(truck_weights[i])
while(bridgeQueue.isNotEmpty()){
answer++
bridgeQueue.poll()
if(waitQueue.isNotEmpty()){
if (bridgeQueue.sum() <= weight - waitQueue.peek()) {
bridgeQueue.add(waitQueue.poll())
} else {
bridgeQueue.add(0)
}
}
}
return answer
}
}
이렇게 풀었습니다
이렇게 하면 통과는 하긴하는대 시간이 너무 느리게 나오더라구요..
테스트 5같은 경우 2464ms 가 나오는 굉장히 느리더라구요..
그래서 다른 분들은 어떻게 하나 찾아봤는대
https://youngest-programming.tistory.com/202
[알고리즘][코틀린] 프로그래머스 다리를 지나는 트럭 -스택, 큐-
https://programmers.co.kr/learn/courses/30/lessons/42583?language=kotlin# 코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니..
youngest-programming.tistory.com
이 분이 푸신 코드를 보고 이 분 코드로 실행해봤는대
제가 짠 코드 보다 훨씬 빠르게 결과를 얻을 수 있었습니다
혹시 시간이 되신다면 저 분 블로그로 들어가서 코드 보고 공부하는 것을 추천합니다!
제가 생각하는 것은 bridgeQueue.sum() 이 메소드가 일반적으로 느려서
제 코드의 결과가 시간이 많이 소요된것으로 예상됩니다!
혹시 더 좋은 코드 나 제 생각이 틀린게 있으면 댓글 적어주시면 감사합니다 ㅎㅎ
'코딩테스트' 카테고리의 다른 글
프로그래머스 부족한 금액 계산하기 코틀린 위클리 챌린지 1주차 (0) | 2021.08.03 |
---|---|
[코딩테스트] 소수찾기 level 1 Java 프로그래머스 (0) | 2021.06.08 |
[코딩테스트] 프로그래머스 프린터 Java level2 (0) | 2021.06.02 |
[코딩테스트] 짝지어 제거하기 Java 프로그래머스 2017 팁스타운 (0) | 2021.05.29 |
[코딩테스트] 기능개발 Java 프로그래머스 스택,큐 level 2 (0) | 2021.05.28 |