[프로그래머스 : 레벨 2] 다리를 지나는 트럭 : Queue(Java)

728x90

이번에 내가 풀어본 문제는 다리를 지나는 트럭이다.

이틀동안이나 붙잡고 어떻게든 풀어서 프로그래머스 조진다 했는데

역시나 조져지는건 나였다.

일단 문제부터 보자.

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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

문제 해석

1. 대기트럭들에 있는 트럭들이 모두 다리를 건너야함

2. 트럭들이 다리를 건너는데 다리가 견딜수 있는 weight를 넘겨선 안됨

3. 다리들은 1초에 1씩 움지이며 bridge_length를 다 건너야함

모든 문제 풀이에서 가장 중요하다고 생각하는건 가장 처음으로 무엇을 할지를 생각해야한다.

위 문제에서 제일 먼저 해야하는것은 대기트럭에서 트럭이 움직이는것이다.

그렇게 하기 위해서는 대기트럭 배열 trucks_weights의 요소에 각각 접근을 해야한다.

1. trucks_weights의 요소에 각각 접근 하기

그럼 이제 우리는 for문으로 trucks_weights의 각각의 요소에 접근을 해야되는거를 알게 되었다.

        for(int tw : truck_weights) {
			//대기트럭 배열의 각각의 요소에 접근하기
        }

그럼 이제 대기트럭에서 트럭을 빼왔는데 그 다음에는 그 안에서 어떤 작업을 하는지를 곰곰히 생각해야한다.

이럴때는 해당 작업 안에서 어떤 작업들을 해야하는지 모두 나열을 해봐야 한다.

1. 다리가 비어 있는지 확인하고 비어 있다면 다리에 트럭 올리기

if(bridge.isEmpty()) { //다리큐에 처음 넣는거라면 진입
        			//다리큐에 집어 넣는것이니 answer++
        			answer++;
        			bridge.offer(tw);
        			checkweight+=tw;
        			System.out.println(answer+"초");
        			System.out.println("다리 : "+ bridge);
        			break; //while 문 밖으로 나가서 다음 트럭을 확인
        		}

2. 다리가 비어있지 않고 다리에 트럭이 꽉차 있는지 확인하고 꽉차있다면 다리에서 맨앞 차량부터 빼내기

else if(bridge.size() == bridge_length) { 
        			//다리 큐 사이즈가 다리 길이랑 똑같다는것은 다리위가 꽉찼다는 뜻임
        			checkweight -= bridge.poll(); //다리 큐에서 맨 앞 삭제
        			System.out.println("맨앞 제거");
        			System.out.println("다리 : "+ bridge);
        		}

3. 다리가 비어 있지 않고 다리에 트럭이 꽉차 있지 않을때 다리위에 트럭을 더 올릴수있는지 확인하고

더 올릴수 없다면 다리위 트럭 다리 끝까지 이동시키기

else {
        			//다리 큐에 트럭을 더했을때 다리 무게 보다 크다면 진입
        			if(checkweight + tw > weight) { 
        				bridge.offer(0); //0을 집어 넣음으로써 트럭을 한칸 앞으로 가게 함
        				answer++; //그리고 트럭도 한칸 앞으로 갔으니 answer 증가
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        			}else {//다리큐에 집어 넣어도 다리 무게보다 적다면 진입
        				bridge.offer(tw); //다리 큐에 넣고
        				answer++;
        				checkweight += tw;
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        				break;//break 시켜거 다음 트럭 확인한다.
        			}
        		}

이렇게 3가지 작업이된다.

위의 작업중 아래의 두 작업은

1. 다리위의 트럭들을 이동시키는 작업

2. 다리 위의 트럭들을 빼내고 다시 다리위에 올릴수있는지 확인하는 작업

모두 반복적으로 이루어 져야 하는 작업이다.

따라서 while(true)를 사용하게 됐고

트럭을 다리위에 올리고 다음 트럭을 받아오는 작업에선 break를 하였다.

그리고 다리위에 올리면 안된다고 했는데 왜 아래 부분에서 다리큐에 집어 넣냐 라고 생각할수 있다.

        			if(checkweight + tw > weight) { 
        				bridge.offer(0); //0을 집어 넣음으로써 트럭을 한칸 앞으로 가게 함
        				answer++; //그리고 트럭도 한칸 앞으로 갔으니 answer 증가
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        			}

위 부분은 다리위에 뭔가 값을 올리는거로 생각할수 있지만 위 소스는 다리 큐에 0이라는 값을 집어넣음으로써

기존에 올라가 있는 트럭을 다리 끝까지 이동시키는 작업이라고 생각할수 있다.

그래서 answer++을 해주는것이다.

그래서 위의 작업들의 소스를 보면 아래와 같다.

       for(int tw : truck_weights) {
        	//while(true)로 계속해서 반복 처리한다.
        	// 다리 큐에 있는 트럭들을 건너게 하기 위해 반복 처리를 했고
        	// 다리가 꽉찼다면 다리위 트럭들을 하나둘씩 빼는 작업을 반복 처리 했다.
        	
        	while(true) {
        		
        		if(bridge.isEmpty()) { //다리큐에 처음 넣는거라면 진입
        			//다리큐에 집어 넣는것이니 answer++
        			answer++;
        			bridge.offer(tw);
        			checkweight+=tw;
        			System.out.println(answer+"초");
        			System.out.println("다리 : "+ bridge);
        			break; //while 문 밖으로 나가서 다음 트럭을 확인
        		}else if(bridge.size() == bridge_length) { 
        			//다리 큐 사이즈가 다리 길이랑 똑같다는것은 다리위가 꽉찼다는 뜻임
        			checkweight -= bridge.poll(); //다리 큐에서 맨 앞 삭제
        			System.out.println("맨앞 제거");
        			System.out.println("다리 : "+ bridge);
        		}else {
        			//다리 큐에 트럭을 더했을때 다리 무게 보다 크다면 진입
        			if(checkweight + tw > weight) { 
        				bridge.offer(0); //0을 집어 넣음으로써 트럭을 한칸 앞으로 가게 함
        				answer++; //그리고 트럭도 한칸 앞으로 갔으니 answer 증가
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        			}else {//다리큐에 집어 넣어도 다리 무게보다 적다면 진입
        				bridge.offer(tw); //다리 큐에 넣고
        				answer++;
        				checkweight += tw;
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        				break;//break 시켜거 다음 트럭 확인한다.
        			}
        		}
        	}
        }

위의 작업에서 나오게 되는 순간은 대기트럭에 있는 마지막트럭을 다리위에 올리고 break; 됐을때이다.

그렇게 됐을때 우리는 마지막에 올린 트럭도 다리를 건너게 해야하기 때문에

answer + bridge_length; 를 해줘야 한다.

return answer + bridge_length;

최종 소스

    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        
        //다리 큐
        Queue<Integer> bridge = new LinkedList<Integer>();
        
        //트럭 총 무게 체크
        int checkweight = 0;
        
        //1. 다리위에 차량을 한대씩 올린다.
        for(int tw : truck_weights) {
        	//while(true)로 계속해서 반복 처리한다.
        	// 다리 큐에 있는 트럭들을 건너게 하기 위해 반복 처리를 했고
        	// 다리가 꽉찼다면 다리위 트럭들을 하나둘씩 빼는 작업을 반복 처리 했다.
        	
        	while(true) {
        		
        		if(bridge.isEmpty()) { //다리큐에 처음 넣는거라면 진입
        			//다리큐에 집어 넣는것이니 answer++
        			answer++;
        			bridge.offer(tw);
        			checkweight+=tw;
        			System.out.println(answer+"초");
        			System.out.println("다리 : "+ bridge);
        			break; //while 문 밖으로 나가서 다음 트럭을 확인
        		}else if(bridge.size() == bridge_length) { 
        			//다리 큐 사이즈가 다리 길이랑 똑같다는것은 다리위가 꽉찼다는 뜻임
        			checkweight -= bridge.poll(); //다리 큐에서 맨 앞 삭제
        			System.out.println("맨앞 제거");
        			System.out.println("다리 : "+ bridge);
        		}else {
        			//다리 큐에 트럭을 더했을때 다리 무게 보다 크다면 진입
        			if(checkweight + tw > weight) { 
        				bridge.offer(0); //0을 집어 넣음으로써 트럭을 한칸 앞으로 가게 함
        				answer++; //그리고 트럭도 한칸 앞으로 갔으니 answer 증가
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        			}else {//다리큐에 집어 넣어도 다리 무게보다 적다면 진입
        				bridge.offer(tw); //다리 큐에 넣고
        				answer++;
        				checkweight += tw;
            			System.out.println(answer+"초");
            			System.out.println("다리 : "+ bridge);
        				break;//break 시켜거 다음 트럭 확인한다.
        			}
        		}
        	}
        }
        //다리길이 만큼 더한 이유는 위의 반복문에서는 항상 마지막걸 다리 큐에 올리고 반복문이 종료된다.
        //그런 상황에서는 마지막건 다리 길이 만큼의 다리를 건너야 하기 때문에
        //기존에 지나갔던 시간(answer)에다가 다리길이를 더한것이다.
        return answer + bridge_length; 
    }

느낀점

1. 다음부터 문제에 대한 접근을 좀 더 단계적으러 나누고 해당 작업에서 무슨 작업을 해야하는지 생각해보자.

2. 한 문제를 너무 오래 붙들고 있지말자. 최대 하루

3. 무언가를 count해야할때는 뭘 몇번동안 반복작업할지 곰곰히 생각 해보자.

4. count는 해야하고 무언가를 이동시켜야 하는데 특정 조건에 이동시키지 못할때 0을 집어 넣어보자.

5. n개가 길이가 1이상인 n을 건널땐 n+(n-1)이다.

6. 해당 문제에 어떤 케이스들이 있을수 있는지 생각해보자.

저작자표시 비영리 변경금지

'코딩일기 > 알고리즘' 카테고리의 다른 글

[자료구조] 힙(Heap) 이란 (0)	2021.05.27
[프로그래머스 : 레벨2] 주식가격 (Java) (0)	2021.05.27
[프로그래머스 : 레벨2] 프린터(java) (0)	2021.05.22
[프로그래머스 : 레벨2] 기능개발 : 큐 사용(Java) (0)	2021.05.21
[프로그래머스 : 레벨 3] 베스트 앨범 : List를 이용한 정렬(Java) (2)	2021.05.21

개척 라이프

[프로그래머스 : 레벨 2] 다리를 지나는 트럭 : Queue(Java)

'코딩일기 > 알고리즘' 카테고리의 다른 글

티스토리툴바

[프로그래머스 : 레벨 2] 다리를 지나는 트럭 : Queue(Java)

'코딩일기 > 알고리즘' 카테고리의 다른 글

관련글

티스토리툴바