2018년 하반기 카카오 공채 1차 문제가 공개되었습니다.
이번에 사용한 플랫폼은 그렙 사에서 만든 Programmers 입니다. 당시 과 교수님이 대표로 하셔서 학교를 다닐 때 10달 정도 재택 형태로 일했던 곳인데, 이제 굴지의 대기업들의 채용 플랫폼을 제공해줄 정도로 커졌다는 점이 매우 기쁘네요.
우선 총평을 하자면 2017년 1차 시험문제보다는 난이도가 올라간 것으로 보입니다. 3번 문제부터 정답율이 상당히 떨어지고 있으며, 블로그에 쓰인대로 간단히 구현만 하면 끝나는게 아니라 효율성 테스트라는 것을 도입하여, 테스트 케이스에 따라 통과된 만큼 부분점수들을 가져갈 수 있는 시스템이 추가되었습니다.
더구나 문제를 풀어볼 수도 있어 저도 제가 제대로 풀었는지 몰랐던 지난 포스팅과 달리 확실하게 풀어볼 수 있어서 좋았던 것 같습니다. 1번부터 보겠습니다.
문제를 요약하면, id와 닉네임이 주어진 유저들이 입장 또는 퇴장을 할 수 있으며, 입장한 유저들은 닉네임을 변경할 수 있고, 닉네임을 변경하면 기존의 기록도 모두 변경될 때, 모든 동작을 다 수행한 후 채팅창에 남은 최종 기록을 출력하는 문제입니다.
채팅창의 내용을 매번 기록하게 되면 로그가 늘어날 때마다 들어온 로그의 길이만큼 시간복잡도가 늘어나게 됩니다. 최악의 경우가 주어질 경우 $O(n^2)$의 시간복잡도로 문제를 풀게 되어, 10만개의 테스트 케이스를 통과할 수는 없을 것입니다.
여기서는 채팅방의 로그와 유저의 정보를 따로 관리하여, 모든 로그를 받은 다음 유저의 정보를 기록에 맵핑시켜주는 방식으로 채팅로그의 개수 N과 유저의 수 K에 대해 $O(NK)$에 풀 수 있습니다. 유저를 바이너리 트리 형태로 관리하게 된다면 $O(NlogK)$로 풀 수 있게 됩니다.
아래에서는 공백을 기준으로 command를 직접 구하는 방법으로 풀었는데, stringstream을 이용한다면 더욱 간단하게 풀 수 있습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <string>
#include <map>
#include <utility>
#include <vector>
using namespace std;
vector<string> solution(vector<string> record) {
vector<string> answer;
vector<pair<string, string> > chat;
map<string, string> user;
int logIdx = 0;
for (string log : record) {
int idx = 0;
string command[3];
for(char c : log) {
if(c==' ') idx++;
else command[idx]+=c;
}
if(command[0] != "Change") {
chat.push_back({command[0],command[1]});
}
if(command[0] != "Leave") {
user[command[1]] = command[2];
}
}
for (auto log : chat) {
string msg = "";
if (log.first == "Enter") {
msg = user[log.second] + "님이 들어왔습니다.";
}
else if (log.first == "Leave") {
msg = user[log.second] + "님이 나갔습니다.";
}
answer.push_back(msg);
}
return answer;
}