[프로그래머스/Level3] [1차] 셔틀버스 (JAVA)

📖 문제

프로그래머스

 

 

 

 

💡  풀이 방식

• 우선순위 큐

필요 자료구조
- 도착 시간을 "분"으로 변환한 값을 저장한 우선순위 큐
- 현재 시간, 마지막 시간, 셔틀버스 탑승 인원 시간 저장용 변수

 

 

1. 크루들의 도착 시간을 "분"으로 변환해 우선순위 큐에 저장한다.

2. 현재 시간, 마지막 시간, 셔틀버스 탑승 인원 저장용 변수를 사용한다.

  - 현재 시간 : 오전 9시로 시작하고, 셔틀버스가 지나갈 때마다 t시간만큼 더한다.

3. 우선순위 큐에서 크루들의 도착 정보를 하나씩 확인하며 계산한다.

  - 가장 빨리 도착한 크루부터 확인한다.

  - 버스 시간보다 이전에 도착했고, 마지막에 셔틀 버스에 탄 인원이 m보다 작다면, 셔틀 버스에 탈 수 있다.

  - 현재 셔틀버스에 크루가 탈 때마다 마지막 시간을 현재 크루의 시간 -1로 재설정한다. (해당 크루보다 1분 먼저 도착하는 게 가장 마지막으로 도착해 해당 버스에 탈 수 있는 시간이므로)

 

 

4. 마지막 버스에 자리가 남는 경우, 해당 버스 도착 시간에 맞춰 나가면 된다.

  - 문제 조건에 9시에 도착한 셔틀은 자리가 있다면 9시에 도착한 크루를 태울 수 있다고 했기 때문

5. 얻은 마지막 시간 정보를 "시간:분"의 형태로 변환해 출력한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        
        // 도착 시간을 "분"으로 변환해 우선순위 큐에 담기
        PriorityQueue<Integer> pq = new PriorityQueue<>();        
        for(String tt : timetable) {
            int time = Integer.parseInt(tt.substring(0, 2)) * 60 + Integer.parseInt(tt.substring(3));
            pq.add(time);
        }
        
        int start = 9*60;   // 현재 시간 (9시로 시작)
        int last = 0;       // 마지막 시간
        int total = 0;      // 셔틀버스 탑승 인원
        
        for(int i = 0 ; i < n ; i++) {
            total = 0;
            
            while(!pq.isEmpty()) {
                int now = pq.peek();
                
                // 버스 시간보다 이전에 도착했고,
                // 마지막에 셔틀 버스에 탄 인원이 m보다 작다면, 셔틀 버스에 탈 수 있음
                if(now <= start && total < m) {
                    pq.poll();
                    total++;
                }
                else {
                    break;
                }
                
                // 마지막 시간을 현재 크루의 시간 -1로 재설정
                last = now - 1;
            }
            
            start += t; // 셔틀버스가 지나갔으니 시간 더하기
        }
        
        // 마지막 셔틀 버스에 탄 인원이 m보다 작다면, 해당 셔틀 버스에 콘이 탈 수 있음
        if(total < m) {
            last = start - t;
        }
        
        // 시간 정보 시간:분 형태로 출력하기
        String hh = String.format("%02d", last/60);
        String mm = String.format("%02d", last%60);
        
        return hh + ":" + mm;
    }
}

 

 

➕ 다른 풀이 방식

- 리스트 배열/리스트를 활용한 풀이 (List<List<Integer>>, List<Integer>[])

[pro] 프로그래머스 level3 17678 셔틀버스 (Java) - 우선순위 큐

[프로그래머스]2018카카오블라인드:[1차] 셔틀버스(java)

 

 

---

💦 어려웠던 점

-  문제 자체를 이해하는 것이 어려웠다.

- 우선순위 큐 사용할 생각을 해야 했다는 것

 

 

🧐 새로 알게 된 내용

- String.format() 메서드 사용법 : String hh = String.format("%02d", last/60); ⇒ 한 자리 숫자인 시간을 두 자리로 만들 때 사용

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스]셔틀버스 - JAVA

 

프로그래머스 셔틀버스 문제 (자바)