[프로그래머스,Level 2] 다리를 지나는 트럭 (JAVA 구현)

2021. 1. 11. 14:34·CodingTest/프로그래머스(Programmers)
반응형

- 첫 풀이

  처음에는 2차원 배열을 활용해 각 트럭이 통과한 시간을 별도로 저장해 모든 처리과정 후, 각 트럭이 다리를 건너는데 걸린 시간을 모두 더하는 방식으로 풀이하고자 하였다. 그러나 실패. 검색을 통해 대략적인 포인트를 확인하고 다시 풀어보았다.

 

- 정답 풀이

  이 문제의 핵심은 다리의 길이라고 생각된다. 입력 예제 1번의 경우 다리의 길이는 2로 총 2대의 트럭이 다리에 올라갈 수 있는데, 이 과정에서 다리가 견딜 수 있는 하중을 고려해주는 것이 포인트 같다. 또한 애초에 문제에서 원하는 답이 모든 트럭이 다리를 지나는데 걸리는 최소 시간이므로, 다리가 견딜 수 있는 하중은 모든 트럭을 견딜 수 있게 주어진다.

 

  고려해야 하는 경우의 수는 아래와 같다.

  1. 첫 번째 트럭이 올라가는 경우 => 트럭은 무조건 올라갈 수 있다. 

  2. n 번째 트럭이 올라가는 경우 => n-1 번째 트럭의 무게 + n 번째 트럭의 무게 < 다리의 하중을 만족해야 함

                                             => n-1 번째 트럭의 무게 + n 번째 트럭의 무게 > 다리의 하중인 경우는 n-1 트럭                                                      만 이동.

  3. 다리의 길이 => 큐의 크기로 판단, 큐의 크기 == 다리의 길이가 되면, 가장 먼저 출발한 트럭이 다리의 끝에 도달.

  (예제 1의 경우, 다리의 길이는 2이며 무게가 7인 첫 번째 트럭이 다리 끝에 도달하는데 2초가 걸림.) 

 

  이정도의 개념을 가지고 코드를 보면 이해하기 쉬울 것 같다.

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // 1. 마지막 트럭을 제외한 모든 트럭이 다리를 통과하는 데 걸린 시간.
        int answer = 0; 
        // 2. 현재 다리의 트럭 무게 총합, 트럭들의 무게를 참조 할 변수.
        int temp_weight = 0, idx=0;
        // 3. 다리, 큐로 구현.
        Queue<Integer> queue = new LinkedList<>();           
        
        // 4. 마지막 트럭을 제외한 모든 트럭을 통과시키기 위한 무한 반복.
        while(true){
            // 5. 마지막 트럭이 다리에 올라갔을 때, 벗어난다.
            if(idx == truck_weights.length)break;
            // 6. 다리에 있는 트럭이 끝에 도달하면, 도달한 트럭의 무게를 현재 다리의 트럭 무게 총합에서 빼준다.
            if(queue.size() == bridge_length){
                temp_weight-=queue.poll();                
            }
            // 7. 현재 다리의 트럭 무게 총합 + 다리에 올라가야 하는 트럭의 무게 > 다리의 하중인 경우.
            else if(temp_weight+truck_weights[idx]>weight){
                // 7-1. 다리의 길이를 고려하기 위해 0인 값을 넣어 자리를 채우고, 1초 증가.
                queue.offer(0);
                answer++;
            // 8. 위를 제외하고는 다리에 트럭이 올라간다.               
            }else{
                queue.offer(truck_weights[idx]);
                temp_weight+=truck_weights[idx];
                answer++;
                idx++;
            }            
        }
        
        // 9. 마지막 트럭이 다리에 올라간 상태에서 다리의 길이를 더해주면, 모든 트럭이 통과하는데 걸린 시간.
        return answer + bridge_length;
    }
}

  

 

 

  

 

저작자표시 (새창열림)
'CodingTest/프로그래머스(Programmers)' 카테고리의 다른 글
  • [프로그래머스,Level 2] 주식가격(JAVA 구현)
  • [프로그래머스,Level 2] 기능개발(JAVA 구현)
  • [프로그래머스,Level 2] 멀쩡한 사각형 (JAVA 구현)
  • [프로그래머스,Level 2] 스킬트리 (JAVA 구현)
뜸부깅
뜸부깅
코딩에 대한 여러 개인적인 생각을 정리하고 공부를 하는 공간입니다!!
  • 뜸부깅
    코오오딩
    뜸부깅
  • 전체
    오늘
    어제
    • Note (429)
      • Skill (31)
        • Java & Spring (9)
        • Javascript & HTML & CSS (0)
        • React (0)
        • Next.js (22)
      • CodingTest (389)
        • 백준 온라인 저지(BOJ) (140)
        • 프로그래머스(Programmers) (79)
        • LeetCode (170)
      • Algorithm & Data Structure (6)
      • [Project] 포트폴리오 (3)
        • Front end (3)
        • Back end (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Easy
    알고리즘
    leetcode 2236
    boj1427
    백준
    백준1427
    프로그래머스
    boj2108
    meidum
    백준7576자바
    medium
    백준1260
    Java
    백준2751
    백준7576
    자바
    next 14
    TypeScript
    BOJ
    component-scan
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
뜸부깅
[프로그래머스,Level 2] 다리를 지나는 트럭 (JAVA 구현)
상단으로

티스토리툴바