[JAVA/프로그래머스] 스택/큐_다리를 지나는 트럭

👀 문제

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

👊 첫 번째 도전

1. 설계

큐를 이용해 다리를 지나고 있는 트럭을 관리한다.
트럭의 무게와 다리를 지나는 시간을 인자로 가지는 클래스 Truck을 생성한다.
다리에 다음 트럭이 들어올 자리가 있다면 큐에 삽입한다.
큐를 순회하며 트럭에게 1초씩 추가하고, 경과시간이 다 채워지면 큐에서 삭제한다. answer에도 1을 추가하여 다리 건너는 시간을 측정한다.
마지막 트럭까지 다리를 건넌다면 while문을 빠져나와 answer을 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Queue;
import java.util.LinkedList;
/**
 *
 * @author HEESOO
 *
 */
class Truck{
    int weight;
    int time;
    public Truck(int w, int t){
        this.weight=w;
        this.time=t;
    }
}
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Truck> q=new LinkedList<Truck>();

        int q_weight=0;
        int truck_idx=0;
        while(true){
            if(truck_idx<truck_weights.length&&q_weight+truck_weights[truck_idx]<=weight){//다리에 다음 트럭이 들어올 자리가 있다면
                q.offer(new Truck(truck_weights[truck_idx],0));
                q_weight+=truck_weights[truck_idx];
                truck_idx++;
            }
            for(Truck t:q){//1초 추가
                t.time++;
                answer++;
                if(t.time==bridge_length){//경과시간이 다 채워지면 삭제
                    q.poll();
                }
            }
            if(truck_idx-1==truck_weights.length&&q.isEmpty()){
                    break;
            }
        }
        return answer;
    }
}

3. 결과

실행결과 실패. 오류 발생.

4. 문제점

해당 오류는 수정을 허용하지 않는 객체를 수정할 때 발생하는 exception이다. 라인29 for문에서 큐의 모든 Truck을 순회하는데, if 조건문으로 큐의 원소가 삭제되면 큐의 크기와 for문 인덱스의 불일치 때문에 에러가 발생한다. 따라서 Iterator를 이용하여 루프 도중 아이템을 오류없이 삭제해야 한다. 또한, 라인36에서 if 조건이 truck_idx==truck_weight.length-1로 바뀌어야 하고, 바뀐다 해도 truck_idx가 마지막이지만 아직 마지막 아이템을 사용하지 않았으며 큐가 비어있을 경우에 break에 걸려 종료될 수 있다(테스트1).

👊 두 번째 도전

1. 설계

다리는 건너는 트럭(q_bridge)과 대기 트럭(q_wait)을 저장하는 큐를 두 개 선언한다.
대기 트럭에 Truck형태로 값을 넣은 후, 조건이 맞을 때 q_bridge에 넣는다.
Iterator를 사용하여 경과시간이 다 된 트럭은 삭제한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Queue;
import java.util.LinkedList;
import java.util.Iterator;
/**
 *
 * @author HEESOO
 *
 */
class Truck{
    int weight;
    int time;
    public Truck(int w, int t){
        this.weight=w;
        this.time=t;
    }
}
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        Queue<Truck> q_bridge=new LinkedList<Truck>();
        Queue<Truck> q_wait=new LinkedList<Truck>();
        for(int w:truck_weights){
            q_wait.offer(new Truck(w,0));
        }
        q_bridge.offer(q_wait.poll());
        int bridge_weight=q_bridge.peek().weight;
        while(!q_bridge.isEmpty()){
            if(!q_wait.isEmpty()&&bridge_weight+q_wait.peek().weight<=weight){
                bridge_weight+=q_wait.peek().weight;
                q_bridge.offer(q_wait.poll());
            }
            Iterator iter=q_bridge.iterator();
            while(iter.hasNext()){
                Truck t=(Truck)iter.next();
                t.time++;
                if(t.time==bridge_length){
                    bridge_weight-=t.weight;
                    iter.remove();
                }
            }
            answer++;
        }
        return answer;
    }
}

3. 결과

실행결과 실패.

4. 문제점

while문을 시작하기 전에 q_bridge에 처음 값을 넣으므로 answer은 1부터 시작해아한다. while(!q_bridge.isEmpty())가 잘못되었다. 테스트1에서 7이 다리를 홀로 건너는데, 다 건너고 나면 q_bridge는 0이 되고, 뒤에 트럭이 더 남아있지만 while문을 종료하기 때문이다.

👊 세 번째 도전

1. 설계

answer은 1로 초기화한다.
while문을 true로 바꾼 후, 두 큐가 다 비었을 때 while문을 종료하게 한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Queue;
import java.util.LinkedList;
import java.util.Iterator;
/**
 *
 * @author HEESOO
 *
 */
class Truck{
    int weight;
    int time;
    public Truck(int w, int t){
        this.weight=w;
        this.time=t;
    }
}
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        Queue<Truck> q_bridge=new LinkedList<Truck>();
        Queue<Truck> q_wait=new LinkedList<Truck>();
        for(int w:truck_weights){
            q_wait.offer(new Truck(w,0));
        }
        q_bridge.offer(q_wait.poll());
        int bridge_weight=q_bridge.peek().weight;
        while(true){
            if(!q_wait.isEmpty()&&bridge_weight+q_wait.peek().weight<=weight){
                bridge_weight+=q_wait.peek().weight;
                q_bridge.offer(q_wait.poll());
            }
            Iterator iter=q_bridge.iterator();
            while(iter.hasNext()){
                Truck t=(Truck)iter.next();
                t.time++;
                if(t.time==bridge_length){
                    bridge_weight-=t.weight;
                    iter.remove();
                    System.out.println(answer+"분에 "+t.weight+"나감");
                }
            }
            answer++;
            if(q_bridge.isEmpty()&&q_wait.isEmpty()){
                break;
            }
        }
        return answer;
    }
}

3. 결과

실행결과 테스트3에서 실패. 이 테스트에서는 1초마다 트럭이 모두 들어온 후 100초부터 하나씩 나가야하는데 100초에 두 개가 나갔다.

4. 문제점

1초일 때 while문 밖에서 q_bridge에 처음 트럭을 넣으므로 첫 while문 방문 시에는 아무 것도 넣으면 안된다.

👊 네 번째 도전

1. 설계

while문 첫 방문 시에는 q_bridge에 트럭을 넣지 않는다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Queue;
import java.util.LinkedList;
import java.util.Iterator;
/**
 *
 * @author HEESOO
 *
 */
class Truck{
    int weight;
    int time;
    public Truck(int w, int t){
        this.weight=w;
        this.time=t;
    }
}
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        Queue<Truck> q_bridge=new LinkedList<Truck>();
        Queue<Truck> q_wait=new LinkedList<Truck>();
        for(int w:truck_weights){
            q_wait.offer(new Truck(w,0));
        }
        q_bridge.offer(q_wait.poll());
        int bridge_weight=q_bridge.peek().weight;
        while(true){
            if(answer!=1&&!q_wait.isEmpty()&&bridge_weight+q_wait.peek().weight<=weight){
                bridge_weight+=q_wait.peek().weight;
                q_bridge.offer(q_wait.poll());
            }
            Iterator iter=q_bridge.iterator();
            while(iter.hasNext()){
                Truck t=(Truck)iter.next();
                t.time++;
                if(t.time==bridge_length){
                    bridge_weight-=t.weight;
                    iter.remove();
                }
            }
            answer++;
            if(q_bridge.isEmpty()&&q_wait.isEmpty()){
                break;
            }
        }
        return answer;
    }
}

Queue q_bridge: 다리를 건너는 트럭을 넣는 큐이다.
Queue q_wait: 대기 중인 트럭들이다.
int bridge_weight: 현재 다리를 건너고 있는 트럭들의 무게이다.
Iterator iter: q_bridge의 원소들을 접근하기 위한 이터레이터이다.

3. 결과

실행결과 🤟 성공 🤟

👏 해결 완료!

데이터를 루프로 순회하고 있을 때 안전하게 삭제하는 Iterator를 배웠다. 테스트3이 안되는 이유를 몰라서 고민을 했었는데, 역시 컴퓨터는 거짓말을 하지 않는다….^ㅠ^

참고

루프 도중 안전하게 삭제하기 https://offbyone.tistory.com/170
java.util.concurrentModificationException이 발생했을 경우! https://devnumgo.tistory.com/entry/javautilconcurrentModificationException%EC%9D%B4-%EB%B0%9C%EC%83%9D%ED%96%88%EC%9D%84-%EA%B2%BD%EC%9A%B0

Menu

👀 문제

👊 첫 번째 도전

1. 설계

2. 구현

3. 결과

4. 문제점

👊 두 번째 도전

1. 설계

2. 구현

3. 결과

4. 문제점

👊 세 번째 도전

1. 설계

2. 구현

3. 결과

4. 문제점

👊 네 번째 도전

1. 설계

2. 구현

3. 결과

👏 해결 완료!

참고