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


작성일 : 2018-06-05 01:46:52
조회수 : 1139



본문

4번 문제는 다소 복잡한 구현 난이도를 가지고 있습니다. 음계에 #이 붙은 경우를 처리해 주어야 하고, 주어진 시간동안 해당 음계가 반복하며 재생된다는 점을 참고하여 실제 재생된 구간의 길이를 구해야 하고, 어찌어찌 찾게 되면 또 조건에 맞는 대상을 찾아 최종적으로 1개를 리턴해 주어야 하는.. 복잡 of 복잡 문제라고 볼 수 있습니다.


C++의 경우 split을 직접적으로 해주는 함수가 없어 더욱 구현 난이도가 올라갈 것 같습니다. 여기서는 다소 간단한 방법으로 split 함수를 구현하여 사용해 보았습니다. 쉼표를 기준으로 split, :를 기준으로 시간 split 하여 이를 객체화하고, 조건에 맞는 순서대로 정렬하여 그 순서대로 찾으면 됩니다. 구현 난이도에 있어 쉽지 않음을 알 수 있습니다.


vector<string> split(string str, char delim)

{

    vector<string> ret;

    int lidx = 0, ridx=0, len = 0;

    for (char c : str)

    {

        if (c == delim)

        {

            ret.push_back(str.substr(lidx, len));

            ridx++; lidx = ridx; len = 0;

            continue;

        }

        ridx++;

        len++;

    }

    ret.push_back(str.substr(lidx, len));

    return ret;

}

class Node

{

public:

    vector<string> arr;

    int no, st, ed;

    string music;


    bool operator < (const Node &n) const

    {

        return (ed - st) == (n.ed - n.st) ? no < n.no : (ed - st) < (n.ed - n.st);

    }

};

string solve(string m, vector<string> musicinfos)

{

    vector<Node> vn(musicinfos.size());

    int i = 0;

    for (auto musicinfo : musicinfos)

    {

        vn[i].no = i;

        vn[i].arr = split(musicinfo, ',');

        auto ststr = split(vn[i].arr[0], ':'), edstr = split(vn[i].arr[1], ':');

        vn[i].st = stoi(ststr[0]) * 100 + stoi(ststr[1]),

        vn[i].ed = stoi(edstr[0]) * 100 + stoi(edstr[1]);

        i++;

    }

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

    

    for (auto it : vn)

    {

        string cmp = "";

        for (int i = 0; it.st < it.ed; i = (i + 1) % it.arr[3].length(), it.st++)

        {

            if (it.arr[3][i] == '#') it.st--;

            cmp += it.arr[3][i];

        }

        if (cmp.find(m) != string::npos) return it.arr[2];

    }

}

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