2019 KAKAO BLIND RECRUITMENT (오픈채팅방)

이 문제는 record가 주어지고 각각을 공백으로 구분했을때 첫번째는 타입, 두번째는 유저 아이디, 세번째는 닉네임이 주어진다. 각각의 타입에 맞게 결과를 기록 및 유저 아이디를 변경 해야한다.

 

구현을 하기 앞서 문제 분석을 먼저 하였다. (특히 프로그래머스 문제는 문제 길이가 길고 이해 하는데 어려움이 있다.)

 

아이디어

문제 구현에 필요한 변수부터 생각해보자.

1. record에 포함된 내용은 각각 "타입", "유저 아이디", "닉네임"이므로 이 3개를 저장할 변수가 필요하다.

2. 결과를 저장할 배열이 필요하다. => vector<string> answer

3. 타입에 따라 특정 유저 아이디의 닉네임을 저장할 공간이 필요하다. => map<string,string> m

• 상태를 그냥 배열에 pair<유저 아이디,닉네임> 이렇게 저장할경우 Change 타입시 모든 배열을 순회 하면서 유저 아이디를 찾아야하기 때문에 O(n)의 시간 복잡도가 된다.
• 물론 입력 크기가 크지 않아 가능하지만 Map을 사용하면 특정 유저 아이디에 대한 닉네임을 O(logN)의 시간 복잡돌 탐색할 수 있다.

4. 결과를 만들어주기 위한 배열이 필요하다. => vector<pair<string,string>> 

• 내가 생각한 방법은 map에 저장 되어있는 유저 아이디의 닉네임을 가져와서 결과를 합쳐주는 것이다.
• m.at(유저 아이디)를 하면 해당 유저 아이디의 닉네임이 나온다. 이를 최종적으로 "님이 들어왔습니다.", "님이 나갔습니다" 와 합쳐준다.
•  ex) answer.push_back(m.at(p.first)+p.second);

풀이

문제를 조건에 맞게 구현하기 위해 가장 먼저 해야할 것은 입력 문자열을 파싱하는것이다. 파이썬을 이용하면 split()이라는 내장 함수를 사용하면 편리하지만 c++에는 따로 구현해주어야 한다.

 

c++의 map에는 insert, insert_or_assign두가지 함수가 존재한다. insert는 만약 해당 map에 중복된 키가 존재하면 Bool false를 반환한다. 반면 insert_or_assign은 중복되 키가 존재할경우 새로운 값으로 대채시켜준다.

 

우리는 문제에서 Change 타입을 받았을때 기존의 유저 아이디의 닉네임을 새로운 닉네임으로 교체 해야 한다. 따라서 insert_or_assign을 사용하여 문제를 해결할 수 있다.

 

구현

#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

vector<string> split(string s){
    vector<string> result;
    stringstream ss(s);
    string tmp;
    
    while(getline(ss,tmp,' ')){
        result.push_back(tmp);
    }
    return result;
}

vector<string> solution(vector<string> record) {
    vector<string> answer;
    vector<pair<string,string>> v;
    map<string,string> m;
    
    for(auto data: record){
        vector<string> parse = split(data);        
        
        if(parse[0] == "Enter"){
            m.insert_or_assign(parse[1],parse[2]);
            v.push_back({parse[1],"님이 들어왔습니다."});
        }
        if(parse[0] == "Leave"){
            v.push_back({parse[1],"님이 나갔습니다."});
        }
        if(parse[0] == "Change"){
            m.insert_or_assign(parse[1],parse[2]);
        }
    }
    
    for(auto p:v){
        answer.push_back(m.at(p.first)+p.second);
    }
    
    
    return answer;
}

위의 코드를 보면 문자열 파싱 하는 함수를 확인할 수 있다. 물론 위 방법도 크게 어렵지 않지만 더 직관적인 방법이 있어 소개하려고 한다.

 

#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

vector<string> solution(vector<string> record) {
    vector<string> answer;
    vector<pair<string,string>> v;
    map<string,string> m;
    
    for(auto data: record){
        string type,uid,nickName;
        stringstream ss(data); //stringstream은 기본적으로 띄어쓰기를 기준으로 파싱해준다.
        ss>>type; //ss를 순서대로 변수에 할당할 수 있다.
        
        if(type == "Enter"){
            ss>>uid;
            ss>>nickName;
            m.insert_or_assign(uid,nickName);
            v.push_back({uid,"님이 들어왔습니다."});
        }
        if(type == "Leave"){
            ss>>uid;
            v.push_back({uid,"님이 나갔습니다."});
        }
        if(type == "Change"){
            ss>>uid;
            ss>>nickName;
            m.insert_or_assign(uid,nickName);
        }
    }
    
    for(auto p:v){
        answer.push_back(m.at(p.first)+p.second);
    }
    
    
    return answer;
}