· 문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
| 0 | [] | [] | [7, 4, 5, 6] |
| 1 | [] | [7] | [4, 5, 6] |
| 2 | [] | [7] | [4 ,5, 6] |
| 3 | [7] | [4] | [5, 6] |
| 4 | [7] | [4, 5] | [6] |
| 5 | [7, 4] | [5] | [6] |
| 6 | [7, 4, 5] | [6] | [] |
| 7 | [7, 4, 5] | [6] | [] |
| 8 | [7, 4, 5, 6] | [] | [] |
· 제한 조건
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 |
· Thinking 1
<고려사항>
- 완전히 지난시점 값을 반환해야되는 거..
- 1초에 1만큼 지나감
- 여러 대의 트럭이 ing 에 들어갈 수 있음
모든 트럭이 완료(end)될 때 까지
다리의 길이만큼
그럼 각 트럭마다 지난 길이를 검사해야되잖아 ..?
int[] temp = new int[truck_weights.length]; //각 트럭이 지금 몇미터를 지나고 있는지를 담을 배열
ArrayList<Integer> end = new ArrayList<Integer>(); //다리를 다 지난 트럭을 담을 배열
ArrayList<Integer> ing = new ArrayList<Integer>(); //다리를 지나는 중인 트럭을 담을 배열
while (end.size() != truck_weights.length) { //완료된 트럭의 수가 대기 트럭의 수와 같으면 종료
if (weight >= truck_weights[0]) { //다리가 지탱할 수 있는 무게 비교하여 최대한 많이 진행이 되어야함
ing.add(truck_weights[0]); //진행중에 넣음
}
if (temp[0] <= bridge_length) { //다리 길이보다 커지지 않은 경우에는 계속 다리를 지나는 중
temp[0]++; //몇 초 째 다리를 지나는 중인지 증가
} else { //다리를 다 지남
end.add(truck_weights[0]); //완료 목록에 담아줌
}
}
System.out.println(temp[0]);
· Thinking 2
두 개를 해보자..!
다리의 길이 : 2
무게 : 10
트럭의 무게 : 4, 5
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
| 0 | [] | [] | [4, 5] |
| 1 | [] | [4] | [5] |
| 2 | [] | [4, 5] | [] |
| 3 | [4] | [5] | [] |
| 4 | [4, 5] | [] | [] |
완료 : 4
0. 전체 초를 셀 가장 큰 변수를 둬야겠네 (이건 계속 증가 end size와 truck_weight length가 같아질때 까지)
1. 다리 무게 체크해서 가능한 만큼 ing에 담기 (몇초에 담겼는지도 알아야함)
2. i 증가하면서 i가 다리의 길이보다 크면 end에 담고, ing에서 삭제하고, 무게에서도 빼야됨
---> 이때 i는 각 트럭마다 i가 새롭게 주어져야됨
int sec = 0;
while (end.size() != truck_weights.length) {
int muge = 0;
for (int i = 0; i < truck_weights.length; i++) {
muge += truck_weights[i];
if (weight >= muge) {
sec++;
ing.add(truck_weights[i]);
temp[i] = i;
} else {
break;
}
}
for (int i = 0; i < truck_weights.length; i++) {
if(temp[i] <= bridge_length) {
sec++;
temp[i]++;
} else {
sec++;
ing.remove(i);
muge -= truck_weights[i];
end.add(truck_weights[i]);
}
}
System.out.println(end.size());
}
· Thinking 3
다시 생각해보자...ㅠ;;
int sec = 0; //초 세기
int i = -1; //트럭 인덱스
int muge = 0; //현재 다리의 무게
while (end.size() != truck_weights.length) {
i++;
muge += truck_weights[i];
if (weight >= muge) {
ing.add(truck_weights[i]); //달리는중
}
if (temp[i] <= bridge_length) {
temp[i]++;
} else {
ing.remove(i);
muge -= truck_weights[i];
end.add(truck_weights[i]);
}
sec++;
}temp 인덱스가 안맞음..ㅠ
· Thinking 4
import java.util.ArrayList;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
ArrayList<Integer> temp = new ArrayList<Integer>();
ArrayList<Integer> end = new ArrayList<Integer>();
ArrayList<Integer> ing = new ArrayList<Integer>();
int sec = 1; //초 세기
int muge = 0; //현재 다리의 무게
int i = 0; //truck_weight의 변수
int j = 0; //temp의 변수
while (end.size() != truck_weights.length) {
if (i < truck_weights.length) {
muge += truck_weights[i];
if (weight >= muge) {
ing.add(truck_weights[i]);
temp.add(0);
i++;
} else {
muge -= truck_weights[i];
}
}
for (j = 0; j < ing.size(); j++) {
if (temp.get(j) < bridge_length) {
int cnt = temp.get(j)+1;
temp.set(j, cnt);
} else {
end.add(ing.get(0));
muge -= ing.get(0);
ing.remove(0);
temp.remove(0);
sec--;
}
}
sec++;
}
return sec;
}
}정확성 : 30.8 / 어쨌든 몇 개는 맞았으니 좋아해야되는 건지ㅠ;;;
· Thinking 5
if (i < truck_weights.length) {
muge += truck_weights[i];
if (weight >= muge) {
ing.add(truck_weights[i]);
temp.add(0);
i++;
} else {
muge -= truck_weights[i];
}
}
for (j = 0; j < ing.size(); j++) {
if (temp.get(j) < bridge_length) {
int cnt = temp.get(j)+1;
temp.set(j, cnt);
} else {
end.add(ing.get(0));
muge -= ing.get(0);
ing.remove(0);
temp.remove(0);
}
}다리를 건너자마자 다시 다른 트럭이 다리에 들어와야되기 때문에 이걸 따로 두면 안되나봐
그래서 오류가 나나봐
무게를 검사해서 건널 수 있는지 확인하고 ing에 들어감
if (temp.get(j) == bridge_length) {
muge -= ing.get(0);
}temp가 bridge_length 라는 것은 곧 걷넌다는 거. 그렇게 되면은 다음에 들어올 수 있기 때문에 미리 무게를 빼줘야됨
근데 하나 빠지고 나면은 ing.size를 줄여서 temp1을 늘려야되는게 안늘어남..
end에 담아야하는데 하....... 진짜 난잡하게 짤 것 같은데
· 완성 코드
import java.util.ArrayList;
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
ArrayList<Integer> temp = new ArrayList<Integer>();
ArrayList<Integer> end = new ArrayList<Integer>();
ArrayList<Integer> ing = new ArrayList<Integer>();
int sec = 0; // 초 세기
int muge = 0; // 현재 다리의 무게
int i = 0; // truck_weight의 변수
int j = 0; // temp의 변수
while (end.size() != truck_weights.length) {
if (i < truck_weights.length) {
muge += truck_weights[i];
if (weight >= muge) {
ing.add(truck_weights[i]);
temp.add(0);
i++;
} else {
muge -= truck_weights[i];
}
}
for (j = 0; j < ing.size(); j++) {
if (temp.get(j) < bridge_length) {
int cnt = temp.get(j) + 1;
temp.set(j, cnt);
} else if (temp.get(j) != bridge_length+1) {
end.add(ing.get(j));
temp.set(j, bridge_length+1);
}
if (temp.get(j) == bridge_length) {
muge -= ing.get(j);
}
}
sec++;
}
return sec;
}
}진짜 개판으로 짰다..ㅎ;;
통과는 했는데 너무 오래걸려서 어이없고 웃기고 자괴감들고 현타폭발...
이 길 내길 맞나... 난 논리적인 사고가 너무 부족한 듯......................
· 문제 출처
https://programmers.co.kr/learn/courses/30/lessons/42583
알고리즘 연습 - 다리를 지나는 트럭 | 프로그래머스
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서
programmers.co.kr
댓글