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

지니·2021년 10월 18일
0

알고리즘

목록 보기
25/33

문제

https://programmers.co.kr/learn/courses/30/lessons/17678?language=java


풀이

  1. 먼저 셔틀버스 시간표를 만들어준다. 09시부터 t분 간격으로 n회 배치하면 된다. t분씩 더해주다가 분(minute)단위가 60이 넘어가면 시(hour)를 1씩 올려주면 된다.
    (bus[i][0]을 시, bus[i][1]을 분으로 두었다.)
	bus = new int[n][2];
        bus[0][0] = 9;
        bus[0][1] = 0;
        for (int i = 1; i < n; i++) {
            bus[i][0] = bus[i - 1][0];
            bus[i][1] = bus[i - 1][1] + t;
            
            if (bus[i][1] >= 60) {
                bus[i][0] += bus[i][1] / 60;
                bus[i][1] = bus[i][1] % 60;
            }            
        }

  1. 추후 계산하기 쉽게 크루에 대한 입력 정보를 정수화하였다. 나중에 계산을 위해서 먼저 오름차순으로 정렬해주었다.
    (문자열이든 숫자든 입력 값 형식이 일정하므로 다음과 같이 정렬하고 시작해도 문제 없다.)
	Arrays.sort(timetable);
        crew = new int[timetable.length][2];
        
        for (int i = 0; i < timetable.length; i++) {    
            String[] inputs = timetable[i].split(":");
            crew[i][0] = Integer.parseInt(inputs[0]);
            crew[i][1] = Integer.parseInt(inputs[1]);          
        }

  1. 크루를 셔틀버스에 탑승시킨다. 특정 셔틀버스 도착 시간보다 이르거나 같게, 해당하는 크루 중 선착순 m명을 탑승시켰다. 단, 마지막 버스와 최종적으로 남은 크루에 대해서는 별도의 계산이 필요하므로 남겨둔다.
	int j = 0;
        for (int i = 0; i < bus.length - 1; i++) {
            int cnt = m;
            int b1 = bus[i][0];
            int b2 = bus[i][1];
            
            while (cnt > 0 && j < crew.length) {
                int c1 = crew[j][0];
                int c2 = crew[j][1];
                                
                if (b1 * 60 + b2 >= c1 * 60 + c2) {
                    cnt--;
                    j++;
                } else {
                    break;
                }
            }
        }

  1. 마지막 셔틀버스와 크루에 대해서 계산을 진행한다.
  • 위의 과정을 거친 후 남은 크루가 마지막 셔틀 수용 가능 인원보다 많을 수 있다. 이 경우 콘은 마지막으로 탑승하는 인원보다 1분 빠르게 나와 대기해야 한다. (단, 09:00 -> 08:59 와 같은 경우에 대한 처리가 필요하다.)
  • 이렇게 구한 시간이 마지막 셔틀 도착 시간보다 늦을 수 있다. 이 경우 마지막 셔틀 도착 시간으로 당겨야 한다.
	int[] answer = new int[2];
        answer[0] = crew[crew.length - 1][0];
        answer[1] = crew[crew.length - 1][1];
        
        if (crew.length - j < m) {
            answer[0] = bus[bus.length - 1][0];
            answer[1] = bus[bus.length - 1][1];
        } else {
            answer[0] = crew[j + m - 1][0];
            answer[1] = crew[j + m - 1][1] - 1;
            
            if (answer[1] == -1) {
                answer[0]--;
                answer[1] = 59;
            }
        }     
        
        if (bus[bus.length - 1][0] * 60 + bus[bus.length - 1][1] < answer[0] * 60 + answer[1]) {
            answer[0] = bus[bus.length - 1][0];
            answer[1] = bus[bus.length - 1][1];
        }


전체 코드

import java.util.*;

class Solution {
    int[][] bus;
    int[][] crew;
    public String solution(int n, int t, int m, String[] timetable) {
        // 셔틀 초기화
        bus = new int[n][2];
        bus[0][0] = 9;
        bus[0][1] = 0;
        for (int i = 1; i < n; i++) {
            bus[i][0] = bus[i - 1][0];
            bus[i][1] = bus[i - 1][1] + t;
            
            if (bus[i][1] >= 60) {
                bus[i][0] += bus[i][1] / 60;
                bus[i][1] = bus[i][1] % 60;
            }            
        }
        
        // 크루 초기화
        Arrays.sort(timetable);
        crew = new int[timetable.length][2];
        
        for (int i = 0; i < timetable.length; i++) {    
            String[] inputs = timetable[i].split(":");
            crew[i][0] = Integer.parseInt(inputs[0]);
            crew[i][1] = Integer.parseInt(inputs[1]);          
        }
                
        int j = 0;
        for (int i = 0; i < bus.length - 1; i++) {
            int cnt = m;
            int b1 = bus[i][0];
            int b2 = bus[i][1];
            
            while (cnt > 0 && j < crew.length) {
                int c1 = crew[j][0];
                int c2 = crew[j][1];
                                
                if (b1 * 60 + b2 >= c1 * 60 + c2) {
                    cnt--;
                    j++;
                } else {
                    break;
                }
            }
        }
                
        int[] answer = new int[2];
        answer[0] = crew[crew.length - 1][0];
        answer[1] = crew[crew.length - 1][1];
        
        if (crew.length - j < m) {
            answer[0] = bus[bus.length - 1][0];
            answer[1] = bus[bus.length - 1][1];
        } else {
            answer[0] = crew[j + m - 1][0];
            answer[1] = crew[j + m - 1][1] - 1;
            
            if (answer[1] == -1) {
                answer[0]--;
                answer[1] = 59;
            }
        }     
        
        if (bus[bus.length - 1][0] * 60 + bus[bus.length - 1][1] < answer[0] * 60 + answer[1]) {
            answer[0] = bus[bus.length - 1][0];
            answer[1] = bus[bus.length - 1][1];
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("%02d", answer[0]));
        sb.append(":");
        sb.append(String.format("%02d", answer[1]));
        
        return sb.toString();
        
    }
}




처음에 생각보다 따져야 할 요소가 많은 것 같아 고민을 한참 했던 문제다. 어느 정도 규칙을 생각하고 적용하는 것이 중요한 것 같다.

profile
Coding Duck

0개의 댓글