카카오 신입 공채 1차 코딩 테스트 풀이 - 4번문제


작성일 : 2018-06-03 16:09:25
조회수 : 1111



본문

이번 문제부터는 난이도가 중으로 올라갔습니다. 이번 문제에서 다소 까다롭게 여겨지는 부분은 시간 계산과 규칙 지정입니다. 먼저 규칙부터 지정해 보겠습니다. 버스에 탑승할 수 있는 가장 늦은 시간을 구할 때, 다음과 같은 경우에 항상 해당됩니다.


1) 운행버스에 탑승객이 모두 타지 못하는 경우


2) 운행버스에 1개 이상의 시간대에 온 탑승객이 모두 타는 경우


3가지 경우에서 각각의 최적 시간은 언제일까요? 1번의 경우, 버스와 동시에 오면 항상 탈 수 있고 이게 가장 늦은 시간이 됩니다. 2번째의 경우, 특정 시간대의 사람이 탑승하여 꽉차게 되면, 그 시간대의 사람 -1분에 탑승하면 됩니다. 예를 들어 3명이 탈 수 있는 버스에 09:09, 09:10, 09:10, 09:11 분에 온 탑승객이 있다면, 09:09분에는 와야 됩니다. 


규칙을 정립하고, 문제를 쉽게 풀기 위해 숫자로 변경하겠습니다. 원리는 간단합니다. 18:01 분이라면 :를 뺀 나머지를 숫자로 처리하면 됩니다. 위의 경우는 1801이 되겠네요. 이런식으로 모든 사람들의 시간을 숫자로 변경한 후, sort를 진행하여 맨 앞의 사람부터 실제로 버스에 태워보면 됩니다.


단 몇 가지 주의해야 할 상황이 있는데요. 00:00 분이 0이기 때문에 여기서 1분을 빼면 -1이 됩니다. 이럴 때는 2400(24:00) 을 더하여 보정을 하면 됩니다. 또 뒤의 2자리가 60 이상일 경우 시간을 더해줘야 하기 때문에 여기서도 적절한 처리를 해주면 됩니다.


string solve(int n, int t, int m, vector<string> timetable) {

    vector<int> cvtTimetable;


    for (auto time : timetable) {

        int cvt = (time[0] - '0') * 1000 + (time[1] - '0') * 100 + (time[3] - '0') * 10 + time[4] - '0';

        cvtTimetable.push_back(cvt);

    }


    sort(cvtTimetable.begin(), cvtTimetable.end());

    int startTime = 900, ans = 0;


    for (int i = 0, j = 0; i < n; i++) {

        int cm = 0, cmp=0;

        map<int, int> timetype;    

        while (cm < m && j<timetable.size()) {

            if (cvtTimetable[j] > startTime) break;

            timetype[cvtTimetable[j]]++;

            j++;

            cm++;

        }

        if (cm < m) {

            ans = max(ans, startTime);

        }

        else {

            int chk = 0;

            for (auto it : timetype) {

                if (chk + it.second >= m) {

                    cmp = it.first - 1;

                    if (cmp % 100 > 59) cmp -= 40;

                    if (cmp < 0) cmp += 2400;

                    break;

                }

                chk += it.second;

            }

            ans = max(ans, cmp);

        }

        startTime += t;

        if (startTime % 100 > 59) {

            startTime += 100, startTime -= 60;

        }

    }

    string cvtans = "";

    auto hh = to_string(ans / 100), mm = to_string(ans % 100);

    if (hh.length() < 2) hh = "0" + hh;

    if (mm.length() < 2) mm = "0" + mm;

    return hh + ":" + mm;

}

카카오 신입 공채 1차 코딩 테스트 풀이 - 4번문제 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.