프로그래머스 문제풀이 (알고리즘) - 셔틀버스

문제

 

난이도 : 중

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

코딩테스트 연습 - [1차] 셔틀버스

 

카카오 해설 (문제 다 풀고 보시면 좋을 듯 합니다)

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

 

풀이

 

단순하게 버스 시간에 도착했을 때 사람이 있으면 버스에 사람을 태워 보기로 했습니다.

그리고 마지막 버스가 도착했을 때 다음과 같은 경우의 수가 있습니다.

마지막 버스에 자리가 남는 경우
마지막 버스에 자리가 남지 않는 경우
  => 마지막에 탑승한 사람보다 1분 빨리 오면 됨

 

참고

 

문제 풀때 시간을 숫자로 변환해서 풀어야 쉽습니다.

예를 들어서 "09:00" 의 시간이 있다면 이 문자열을 가지고 버스를 탈 수 있는지 없는지 시간을 비교하는 것을 어렵기 때문에 다음과 같이 시간을 초로 변환했습니다.

3600 * 9 + 0 * 60 = 32,400

 

정답

 

코드를 객체 지향적으로 풀이하려고 노력 했습니다.

Bus 와 People 별도의 내부 클래스를 만들었습니다.

참고 부탁드립니다

public class Five {
    public String solution(int n, int t, int m, String[] timetable) {

        Arrays.sort(timetable);

        Queue<People> peoples = new LinkedList<>();
        LinkedList<Bus> buses = new LinkedList<>();

        for (String time : timetable)
            peoples.add(new People(time));

        int first = 3600 * 9;
        buses.add(new Bus(first, m));
        for (int i=1; i<n; i++)
            buses.add(new Bus(first + (i * (t * 60)), m));

        Bus bus = null;
        while (!buses.isEmpty()) {
            bus = buses.poll();

            // 사람을 더 태울 수 있으면
            while (bus.canRideMorePeople()) {
                People people = peoples.peek();

                if (people != null && people.getTime() <= bus.getTime())
                    bus.rideThisBus(peoples.poll());
                else
                    break;
            }

        }

        // 마지막 버스에 자리가 남는 경우
        if (bus.canRideMorePeople())
            return timeToString(bus.getTime());

        // 마지막 버스에도 자리가 남지 않으면
        return timeToString(bus.getLastLimitTime());
    }

    public String timeToString(int time) {
        return  String.format("%02d", time / 3600) + ":" + String.format("%02d", ( time % 3600 ) / 60);
    }

    static class People {

        private int time;

        public People(String time) {
            this.time = 3600 * Integer.parseInt(time.split(":")[0]) + 60 * Integer.parseInt(time.split(":")[1]);
        }

        public int getTime() {
            return time;
        }
    }

    static class Bus {
        private int time;
        private int limit;
        private List<People> peoples = new ArrayList<>();

        public Bus(int time, int limit) {
            this.time = time;
            this.limit = limit;
        }

        public int getTime() {
            return time;
        }

        public boolean canRideMorePeople() {
            return peoples.size() < limit;
        }

        public int getLastLimitTime() {
            if (peoples.size() > 0)
                return this.peoples.get(peoples.size() - 1).getTime() - 60;
            else
                return this.time;
        }

        public void rideThisBus(People people) {
            this.peoples.add(people);
        }
    }

}