프로그래머스 - 코딩테스트 연습 : 스택/큐 다리를 지나는 트럭

• 다리를 지나는 트럭

darklight

sublimevimemacs

Java 

문제 설명

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

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

나의 풀이 

public int solution(int bridge_length, int weight, int[] truck_weights) {

        int time = 0; // 1의 이동이 가능한 시간
        int[] position = new int[truck_weights.length]; //각 트럭별 현재 위치
        Arrays.fill(position, 0);
        int curTotalWeight = 0; //현재 다리 위 트럭들의 총 무게
        int passTruck = 0; //현재 통과 트럭 수
        int nextIdx = 0; //다음 통과 순서인 트럭의 인덱스

        while(passTruck < truck_weights.length) //루프 안에서 바로 return을 하기 때문에, 단지 형식에 맞춘 조건
        {
            //=================================디버깅시 현재 상황을 보기 위한 로그 출력 부분
            System.out.println("현재 시간 : " + time);
            System.out.println("현재 총 무게 : " + curTotalWeight);
            System.out.println("현재 트럭들 진행 상황: ");
            System.out.println("======================================================");
            for(int i = 0; i < position.length; i++)
            {
                String col = ",";
                if(i == (position.length-1))
                {
                    col = "";
                }
                System.out.print(position[i] + col);
            }
            System.out.println();
            //=================================디버깅시 현재 상황을 보기 위한 로그 출력 부분

            time++; //로직의 진행을 위한 경과 시간 증가
            for(int i = 0; i < nextIdx; i++) //이미 다리 위에 나와있는 트럭들을 1씩 이동 시키기 위한 for문
            {
                if(position[i] > bridge_length) //이미 도착한 트럭은 연산 필요 없음
                    continue;

                position[i]++; //다리 위 트럭들 1씩 이동
                if(position[i] > bridge_length)  //1 이동한 위치가 다리보다 긴 경우 (도착)
                {
                    //통과한 트럭이 발생 했을 경우 처리
                    passTruck++; //통과 트럭 수 증가
                    curTotalWeight -= truck_weights[i];  //현재 다리 위 총트럭무게에서 제외
                    if(passTruck >= truck_weights.length) //통과한 트럭이 발생한 상태에서, 그 총 수가 대기했던 트럭과 같을 경우
                        return time; //바로 현재 시간 리턴
                }
            }

            if(nextIdx < truck_weights.length) //다음 차례 트럭의 인덱스가 트럭의 총 수보다 작을 경우만 트럭 내보내기 처리
            {
                int nextWgt = curTotalWeight + truck_weights[nextIdx]; //다음 트럭이 나오게 될 경우 다리위 트럭 총 무게

                if(nextWgt <= weight) //다리가 감당 할수 있는 무게일 경우에만
                {
                    //다음 차례 트럭 내보내기 처리
                    position[nextIdx]++;
                    curTotalWeight+= truck_weights[nextIdx];
                    nextIdx++;
                }
            }
        }
        return time;
    }

 

소감

1,2번째 입출력 예까지는 금방 처리를 하였는데, 3번째 처리에서 원치 않는 결과가 나왔고

그 지점을 찾기 위해 break point를 사용하여 찾으려 하였지만, 결과까지 꽤 많은 진행을 해야하므로

일일히 데이터를 확인하기에 어려움이 있어서..

로직의 최초 지점에서 현재 상황을 알 수 있는 콘솔로그를 찍어서 한눈에 로직의 틀린점을 찾을 수 있었다.

 

개선점

잘못된 결과가 나올 경우 로직의 진행 상황을 한눈에 알 수 있는 부분에서 로그를 잘 찍도록 하자.

통과후에 다른 사람들의 로직을 보니까 객체지향을 접목해서 푼 풀이가 있었다.

실제 프로젝트 진행할때를 위해 알고리즘도 객체지향 관점에서 풀어낼수 있도록 노력하자.

 

 

 

 

 

 

문제 출처 : programmers.co.kr/learn/courses/30/lessons/42583