/ CODINGTEST

프로그래머스 코딩테스트 연습 다리를 지나는 트럭(스택/큐) 문제

오늘은 프로그래머스 코딩테스트 연습의 다리를 지나는 트럭 문제를 풀어보았다. 처음에 나는 길이와 트럭의 길이가 문제에 주어져 있지 않아서 트럭의 무게 = 트럭의 길이인줄 알았다. 그래서 헤메다가 다시 문제를 읽어보니 트럭길이가 1이지 않을까 하는 생각이 들어서 대입하여 풀어보았고, 이게 맞긴했다. 처음 내가 풀었던 코드이다.(실패한 코드)
문제 풀어보기

public static int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
Queue<Integer> que = new LinkedList<Integer>();
int tmp=0;
int j = 0;
int i= 0;
while(i<truck_weights.length) {
if(que.peek() == null) {
tmp += truck_weights[i];
que.add(truck_weights[i]);
i++;
j++;
}
if(tmp + truck_weights[i]<=10) {
que.add(truck_weights[i]);
i++;
j++;
}else {
j++;
}
if(j == bridge_length) {
answer += j;
tmp -= que.poll();
j = 0;
}
}
return answer;
}
view raw truck_programmers hosted with ❤ by GitHub
실패한 이유는 다리에 올라가 있는 트럭의 무게가 다리가 견딜수 있는 하중보다 작으면 된다라는 점은 동일했다. 하지만, 문제가 되는 부분은 만약 2대의 트럭이 다리에 올라가 있다고 하고, 다리가 견딜수 있는 하중보다 2대가 같거나 적었을 경우인데, 이중에 한대가 빠져나갔다고하고 다음 들어오는 트럭과 남아있는 한대의 트럭이 합이 하중보다 작을 경우 한대는 끝에 다다르고 한대는 시작점에 있는데 이부분에서 걸리는 시간이 차이가 나는 것이다.
이 부분을 어떻게 맞춰줘야 할까하여, 결국 구글에 해당 답을 찾아보게 되었고, 문제는 간단했다. 큐에 트럭을 담는 것과 무게를 비교해주는 것은 동일했다. 하지만 큐에 트럭만 담아주는 것이 아닌, 다른 수를 넣어(보통 0을 넣으셨다) que.size()를 다리 길이와 맞춰주고 쉽게 한칸씩 앞으로 간다면, 초를 증가시켜 주면 되는 것이었다.
밑에는 아이디어를 받고 다시 작성한 정답 코드이다.
public static int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
int i =0;
int tmp = 0;
Queue<Integer> que = new LinkedList<Integer>();
while(i<truck_weights.length) {
if(que.peek() == null) {
que.add(truck_weights[i]);
tmp += truck_weights[i];
i++;
answer++;
}
if(que.size() == bridge_length) {
tmp -= que.poll();
}else if(i>=truck_weights.length) {
break;
}
if(tmp + truck_weights[i]<=weight) {
que.add(truck_weights[i]);
tmp+=truck_weights[i];
answer++;
i++;
}else {
que.add(0);
answer++;
}
}
answer += bridge_length;
return answer;
}
view raw truck_programmers_solved hosted with ❤ by GitHub

큐를 길이로도 쓸 수 있다!(담고 빼는거만 생각하지말자)