다리를 지나는 트럭 / 프로그래머스 연습문제 / programmers / level2 / 스택,큐 / javascript

programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

이번 문제는 다리를 지나는 트럭들이 지나갈때까지 걸리는 시간을 구하는 문제이다.

 

우선...혼자서 풀이 하였을때는 거의 90%가까이 근접하였으나 도무지 해결방법을 찾지 못하여,

질문하기의 질문들을 어쩔수 없이 참고 하였다. 내 논리력의 부족인가...

시간이 지날 수록 스스로에게 짜증이 나서 너무 대충 생각한 것 같다. 다음에는 차분하게 문제를 풀어봐야지.

 

내 알고리즘 논리의 흐름

1. 다리 배열을 하나 만든다.

2. 대기 트럭을 우선 하나 무조건 빼온다. (왜냐? 트럭이 무게는 초과제한이하이기때문에 1대는 무조건 올라간다.)

3. 빼서 다리배열에 추가해준다. 그리고 시간도 1초 더해준다. (unshift)

4. 그 다음 현재무게 변수를 하나 만들어서 빼온 트럭의 무게를 더해주고 그때마다 다리의 초과중량과 비교해준다.

5. 만약에 더한 무게가 초과중량보다 작으면 다음 트럭을 또 더해주고 크면 해당 트럭은 다시 대기 트럭으로 넣어버린다. (unshift)

5-2. 그리고 현재무게 + 다음트럭이 초과중량보다 큰 상태라면 현재 배열에 있는 트럭들을 빼주고 경과시간에 다리 길이 만큼 더해준다.

6. 대기 트럭이 남아있지 않을 때까지 해당 작업을 반복해준다.

 

결과는 50%만 맞았다.

내 머리속에서는 정답을 외치고 있는데 컴퓨터는 틀렸다고 하니 ㅠㅠ 몇 시간을 고민하다가 처음으로 한계를 느끼고 컨닝을 하였다. 휴..... 여기서 발견된 문제는 이거 였다.

 

경계값 분석의 경우인데 무게, 트럭, 다리길이가 0이거나 트럭인 하나만 있거나 트럭과 다리길이와 무게가 같거나 하는 경우 등등 에서 오류가 발생하는 것이었다.

ㅠㅠ 내 자신에게 화가나서 맥주를 원샷때리고 차분하게 다시 고민하였다.

알코올이 들어오니 자신감이 생기고 머리가 더 돌아가더라.

 

그리하여 흐름을 이렇게 수정하였다.

1. 다리의 배열을 다리의 길이만큼 0을 넣어서 선언해준다.

2. 트럭의 무게를 비교하는건 위와 동일하다.

3. 맨 앞의 트럭을 꺼내서 다리에 맨앞에 unshift로 넣어주고 맨 뒤의 0은 pop으로 제거

4. 이 상태로 이제 반복을 하는데 현재 다리의 무게가 0이 될때까지 반복을 할 것이다. 그러면서 계속 시간을 1초씩 증가시킨다.

5. 다리 길이만큼 다리의 배열을 만들었으니 현재 다리 위에 있는 트럭의 무게 - 다리 배열의 맨뒤값(pop)을 계속 반복해준다. 이런식으로 하면 언젠가는 무게가 0이 된다. 그때 멈춘다.

6. 그리고 무게를 비교하여 작거나 같으면 트럭을 한대 더 추가해주고 그렇지 않으면 계속 지나가게 한다.

7. 그러다가 0이 되었을때 나오는 시간값을 리턴해준다.

 

그리하여 완성된 코드

function test() {

	var _bridge_length = 2;
	var _weight = 10;
    var _truck_weights = [7,4,5,6];

	solution(_bridge_length, _weight, _truck_weights);
}

function solution(bridge_length, weight, truck_weights) {
    let answer = 0;

    let bridge = [];
    // 다리 지나가는 트럭들

    let bridgeChk = 0;
    // 현재 다리의 무게

    for (let i = 0; i < bridge_length; i++) {
        bridge.push(0); 
    }
    // 다리의 길이만큼 다리 배열을 0으로 선언해준다.

    let truck = truck_weights.shift();
    // 무조건 트럭 1대는 다리에 올라오니까 우선 꺼내온다.

    bridge.unshift(truck)
    bridge.pop();
    // 트럭 1대를 다리에 올린다. 올렸으니 맨 마지막 0은 빼준다.

    bridgeChk += truck;
    // 다리 제한 무게 증가

    answer++;
    // 일단 올라갔으니까 무조건 1초는 지난거다.

    while(bridgeChk != 0) {
        console.log(bridge)
        bridgeChk -= bridge.pop();
        // 다리 1칸 이동

        truck = truck_weights.shift();
        // 그 다음 트럭을 하나 꺼내준다.

        if (truck + bridgeChk <= weight) {
        // 꺼내온트럭 + 현재 다리무게가 제한하중보다 같거나 적으면
            bridge.unshift(truck)
            bridgeChk+=truck

        } else {
        // 그렇지 않다는 건 다리에 못들어간다는 뜻, 그럼 이 트럭은 못들어 간다.
            bridge.unshift(0)
            truck_weights.unshift(truck)
            // 그러니 다시 0으로 다리를 초기화 해주고 꺼냈던 트럭을 다시 대기열로 넣어버린다.
        }
        answer++;

    }

    console.log(answer)
    return answer;
}

 

다리 배열을 다리의 길이만큼 초기화 선언 해주는게 내가 참고한 부분이었다.

길이가 길수록 시간이 오래걸린다는 점이 아쉽지만, 그래도 내 코드에서 약간의 수정만으로 가장 근접하게 나올 수 있는 코드였다.

 

자존심 상해 ㅠㅠ 수학 공부좀 해야겠다...

 

---

[깃허브]

https://github.com/RUCKUSJERRY/practiceOfJava/blob/main/Prs_Pratice/src/com/level02/bridgeTruck.js

RUCKUSJERRY/practiceOfJava