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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17678

프로그래머스

 

문제 분석

콘은 게으르기 때문에 가능하면 가장 늦게 버스를 타려고 한다.

버스는 9:00 부터 시작해서 t분 간격으로 n번 운행 되며 버스에 탑승 가능한 인원은 m 명이다.

콘을 제외한 다른 사람들이 버스를 탑승하기 위해 탑승지에 도착하는 시간이 timetable 로 주어진다.

 

 

1번 )

모든 인원 4명이 9:00 전에 도착했으니 9:00 버스를 타고 남은 자리가 있어 콘이 9:00 에 도착한다면 탈수 있다.

 

2번)

9시 버스에 08:00 분에 도착한 인원이 한명 타고 09:10 버스에 09:09, 09:10 에 도착한 사람이 탈 수 있기 때문에 콘이 버스에 타려면 09:09 에는 도착해야 한다.

문제 조건에 같은 시간에 오면 콘은 항상 뒤로 선다는 조건이 있어 09:10 에 도착하면 버스 탑승하지 못한다.

 

3번)

09:00 버스에 2명, 09:01 버스에 2명 타게되면 콘이 타지 못한다. 따라서 콘은 버스를 타기 위해 사람들 보다 1분 빨리와 08:59에 도착해야 한다.

 

...

 

문제 접근

입출력 예제를 하나하나 따라가 보니 다음과 같은 2가지 경우가 나온다는 것을 알게됐다.

 

1. 마지막 버스의 자리가 남았다면, 그 버스 도착 시간이 정답.

2. 마지막 버스의 자리가 남지 않았다면, 마지막 버스의 마지막에 탄 사람보다 1분 일찍 오면 정답.

 

해당 문제를 쉽게 해결하기 위해 string 으로 되어 있는 시간을 전부 int 형의 분 단위로 맞추었다.

 

그 후 도착한 버스마다 탈 수 있는 사람들의 시간을 아래 처럼 기록하였다. 

 

2번 예시)

버스 도착 시간 리스트 : [540, 550]
버스마다 탑승한 고객의 시간 리스트 [[480], [549, 550]]

 

이렇게 기록하고 나면 위의 2조건에 따라 문제를 해결할 수 있다.

마지막 버스를 찾아서 해당 버스에 좌석이 남았는 지 체크하고 남았다면 해당 버스 시간을 정답 형태로 변경하고

그렇지 않다면 해당 버스의 마지막에 탑승한 사람의 시간에서 -1을 한 값을 정답 형태로 변경하면 된다.

 

코드

import java.util.*;

class Solution {
    public String solution(int n, int t, int m, String[] timetable) {
        String answer = "";
        int result = 0;
        List<Integer> timeList = new ArrayList<>();
        List<Integer> busTimeList = new ArrayList<>();
        List<List<Integer>> seatList = new ArrayList<>();
        
        for(String str : timetable){
            String[] split = str.split(":");
            int time = 60 * Integer.parseInt(split[0]) + Integer.parseInt(split[1]);
            timeList.add(time);
        }
        int init = 60 * 9;
        
        for(int i=0; i<n; i++){
            busTimeList.add(init);
            init += t;
        }
        
        Collections.sort(timeList);
        
        for(int i=0; i<busTimeList.size(); i++){
            int busTime = busTimeList.get(i);
            int cnt = m;
            seatList.add(new ArrayList<>());
            while(!timeList.isEmpty() && timeList.get(0) <= busTime && cnt > 0){
                seatList.get(i).add(timeList.get(0));
                timeList.remove(0);
                cnt--;
            }
        }
 
        int lastIdx = busTimeList.size()-1;
        
        if(seatList.get(lastIdx).size() < m){
            result = busTimeList.get(lastIdx);
        }else{
            List<Integer> target = seatList.get(lastIdx);
            System.out.println("tar" + target);
            if(target.size() == 0){
            }else{
                result = target.get(target.size()-1) - 1;
            }
        }
        
        int houre = result / 60;
        int minute = result % 60;
        
        answer = String.format("%02d:%02d", houre, minute);
        return answer;
    }
}

 

후기

문제를 해결하는 56분 정도 걸렸다. 

처음 문제를 이해하는데 시간이 좀 걸렸고 버스마다 태운 사람을 기록하기 위해 처음에는 HashMap<Integer, List<Integer>> 자료구조를 이용했다.

 

하지만 HashMap은 정렬이 되지 않아 List 2개로 쪼개서 인덱스를 이용해서 접근하는 방식으로 바꾸면서 시간을 많이 잡아먹었다...

다시 생각해보니 키 리스트를 빼서 정렬 후 문제를 풀었어도 해결 가능해 보인다.