카카오 신입 공채 1차 코딩 테스트 문제 4.셔틀버스(난이도: 중)

카카오 신입 공채 1차 코딩 테스트 문제 4.셔틀버스(난이도: 중)

카카오 블라인드 채용에 출제된 문제가 공개돼 풀어보았다. 한 문제당 하나의 클래스로 만들었으며 테스트 코드까지 한꺼번에 올린다. 실제 채용 시험의 채점이 어떻게 이뤄졌는지 모르지만, 문제에 나와있는 입출력은 모두 만족하는 코드이다. 강의할 때도 늘 말하는 것이지만, 코드에 정답은 없다. 문제를 푸는 하나의 방법이 될 수 있음을 기억하고 참고하라.

문제 4.셔틀버스(난이도: 중)

문제 설명과 해설은 아래 링크를 참고하라.

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

고려해야 할 사항이 좀 많아서 정답에 정확히 다다르기까지는 좀 시간이 걸렸을 것 같다. 문제 자체에 오류도 있는데 주석으로 달아놨으니 참고해서 보자.

import org.junit.Test;
 
import java.util.ArrayList;
import java.util.Arrays;
 
import static org.junit.Assert.assertEquals;
 
public class Q4 {
    public static void main(String[] args) {
 
 
    }
 
    @Test
    public void question4TestCase1() {
        int n = 1;
        int t = 1;
        int m = 5;
        String[] timeTable = {"08:00",
                "08:01",
                "08:02",
                "08:03"};
        String answer = "09:00";
 
        assertEquals(answer, question4(n, t, m, timeTable));
 
    }
 
    @Test
    public void question4TestCase2() {
        int n = 2;
        int t = 10;
        int m = 2;
        String[] timeTable = {"09:10",
                "09:09",
                "08:00"};
        String answer = "09:09";
 
        assertEquals(answer, question4(n, t, m, timeTable));
    }
 
    @Test
    public void question4TestCase3() {
        int n = 2;
        int t = 1;
        int m = 2;
        String[] timeTable = {"09:00",
                "09:00",
                "09:00",
                "09:00"};
        String answer = "08:59";
 
        assertEquals(answer, question4(n, t, m, timeTable));
    }
 
    @Test
    public void question4TestCase4() {
        int n = 1;
        int t = 1;
        int m = 5;
        String[] timeTable = {"00:01",
                "00:01",
                "00:01",
                "00:01",
                "00:01"};
        String answer = "00:00";
 
        assertEquals(answer, question4(n, t, m, timeTable));
    }
 
    @Test
    public void question4TestCase5() {
        int n = 1;
        int t = 1;
        int m = 1;
        String[] timeTable = {"23:59"};
        String answer = "09:00";
 
        assertEquals(answer, question4(n, t, m, timeTable));
    }
 
    @Test
    public void question4TestCase6() {
        int n = 10;
        int t = 60;
        int m = 45;
        String[] timeTable = {"23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59",
                "23:59"};
        String answer = "18:00";
 
        assertEquals(answer, question4(n, t, m, timeTable));
    }
 
 
    /**
     * @param n         셔틀 운행 횟수
     * @param t         셔틀 운행 간격
     * @param m         한 셔틀에 탈 수 있는 최대 인원
     * @param timeTable 셔틀 대기열에 도착하는 시간
     * @return 콘이 도착해야하는 가장 늦은 시간
     */
    public String question4(int n, int t, int m, String[] timeTable) {
        String answer = "";
        int totalMin = (n - 1) * t;
        int lastHour, lastMin;
        int indexWhoIsTheLastCrew = 0;
 
        ArrayList<String> shuttleTimeTable = new ArrayList<>(Arrays.asList("09:00"));
 
        for (int i = 1; i < (n); i++) {
            shuttleTimeTable.add(getTimeAfterXMinFrom0900(i * t));
        }
 
        lastHour = 9 + totalMin / 60;
        lastMin = totalMin % 60;
 
        String lastShuttle = String.format("%02d", lastHour) + ":" + String.format("%02d", lastMin);
 
        System.out.println("셔틀 마지막 운행 시간 : " + lastShuttle);
 
        System.out.println("셔틀 운행 횟수(n) : " + n + "회");
        System.out.println("셔틀 운행 간격(t) : " + t + "분");
 
        System.out.print("셔틀버스 도착 시간표 : ");
        for (String s : shuttleTimeTable) {
            System.out.print(s + ", ");
        }
        System.out.println();
 
        System.out.println("셔틀 탑승 인원 : " + m + "명");
 
        Arrays.sort(timeTable);
        ArrayList<String> timeTableList = new ArrayList<>(Arrays.asList(timeTable));
 
        System.out.println("탑승 인원 도착 시간 정렬 : ");
        for (String s : timeTableList)
            System.out.print(s + ", ");
        System.out.println();
 
        /*
        TODO. 콘의 버스 탑승 알고리즘
        콘은 마지막 버스를 타면 됨

        도착 버스마다 몇 명이 탈 수 있는지 계산

        마지막 버스는 09:00 + (00:tt * n)에 출발함
        콘은 09:00 + (00:tt * n)에 큐에 들어오면 됨
        단, 09:00 + (00:tt * n) 이전에 오는 대기 인원이 n * m 명 보다 많거나 같으면 대기인원 중 n * m번째로 도착해야 함 = 대기 큐의 n * m번째 도착 시간보다 -1분 먼저 도착하면 됨
         */
 
        // TODO: 문제 오류:콘이 n*m번째 도착 인원과 같은 시간에 도착하면 탈 수 있는지 아닌지에 대한 판단을 할 수가 없음.
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (timeTableList.size() <= indexWhoIsTheLastCrew) {
                    indexWhoIsTheLastCrew = -1;
                    break;
                }
                String shuttleTime = shuttleTimeTable.get(i);
                String crewTime = timeTableList.get(indexWhoIsTheLastCrew);
                if (getHour(crewTime) < getHour(shuttleTime)) {
                    indexWhoIsTheLastCrew++;
                } else if (getHour(crewTime) == getHour(shuttleTime)) {
                    if (getMin(crewTime) <= getMin(shuttleTime)) {
                        indexWhoIsTheLastCrew++;
                    } else {
                        break;
                    }
                } else if (getHour(crewTime) > getHour(shuttleTime)) {
                    break;
                }
            }
        }
 
        if (indexWhoIsTheLastCrew <= 0 || indexWhoIsTheLastCrew > timeTableList.size()) {
            answer = lastShuttle;
        } else {
            answer = getTime1minBefore(timeTableList.get(indexWhoIsTheLastCrew - 1));
        }
        return answer;
 
    }
 
    public int getHour(String s) {
        String[] time;
        time = s.split(":");
        return Integer.parseInt(time[0]);
    }
 
    public int getMin(String s) {
        String[] time;
        time = s.split(":");
        return Integer.parseInt(time[1]);
    }
 
    /**
     * 09:00 에서 min 분 후의 시간 반환
     *
     * @param min
     * @return
     */
    public String getTimeAfterXMinFrom0900(int min) {
 
        if (min <= -60) {
            return String.format("%02d", 8 + (min / 60)) + ":" + String.format("%02d", 60 + (min % 60));
        } else if (min > -60 && min < 0) {
            return String.format("%02d", 8) + ":" + String.format("%02d", 60 + min);
        } else if (min >= 0 && min < 60) {
            return "09:" + String.format("%02d", min);
        } else if (min >= 60) {
            return String.format("%02d", 9 + (min / 60)) + ":" + String.format("%02d", min % 60);
        }
        return "";
    }
 
    @Test
    public void tc00_getTimeAfterXMinFrom0900() {
        String result = getTimeAfterXMinFrom0900(30);
        assertEquals("09:30", result);
    }
 
    @Test
    public void tc01_getTimeAfterXMinFrom0900() {
        String result = getTimeAfterXMinFrom0900(90);
        assertEquals("10:30", result);
    }
 
    @Test
    public void tc02_getTimeAfterXMinFrom0900() {
        String result = getTimeAfterXMinFrom0900(-5);
        assertEquals("08:55", result);
    }
 
    @Test
    public void tc03_getTimeAfterXMinFrom0900() {
        String result = getTimeAfterXMinFrom0900(-90);
        assertEquals("07:30", result);
    }
 
    public String getTime1minBefore(String hhmm) {
        if (getMin(hhmm) > 0) {
            return String.format("%02d", getHour(hhmm)) + ":" + String.format("%02d", getMin(hhmm) - 1);
        } else if (getMin(hhmm) == 0) {
            return String.format("%02d", getHour(hhmm) - 1) + ":" + String.format("%02d", 59);
        }
 
        return "err";
    }
 
    @Test
    public void tc00_getTime1minBefore() {
        String result = getTime1minBefore("09:00");
        assertEquals("08:59", result);
    }
 
    @Test
    public void tc01_getTime1minBefore() {
        String result = getTime1minBefore("10:10");
        assertEquals("10:09", result);
    }
}