알고리즘 :: 프로그래머스 :: 2019 카카오 :: 오픈채팅방 (C++)

오픈채팅방

문제 링크

1. 문제이해

1.1. 문제 출제 의도 파악하기

• C++이 가장 취약한 유형인 문자열 관련 문제입니다.
• 문자열 파싱 구현과 자료구조를 활용할 수 있는 능력을 물어보고 있습니다.

1.2. 문제 해결 과정

1. 문자열 파싱

• 주어지는 문자열은 명령 아이디 닉네임구조로 돼있습니다.
• 띄어쓰기(white space)로 문자열을 파싱해서 명령, 아이디, 닉네임을 따로따로 얻어야 합니다.
• C++에서 문자열을 자르는 방법은 공식처럼 외우면 좋습니다.

2. unordered_map 자료구조 이용

• 유저 아이디는 닉네임과 함께 저장돼야합니다.
  1. vector<pair<string, string>>에 저장하는 방법이 있습니다.
  2. unordered_map<string, string>에 저장하는 방법이 있습니다.
• 여기서는 2번을 사용하는 것이 적절합니다.
  • Change 명령으로 닉네임을 변경할 때, 유저 아이디를 찾은 뒤 닉네임을 변경해야 합니다.
  • 1번을 사용하는 경우 모든 인덱스를 검사해야하지만, 2번을 사용하면 [] 연산으로 바로 접근이 가능합니다.
  • 유저 아이디는 겹쳐서는 안되기 때문에 uniqueness를 보장하는 map를 사용하는 것이 좋습니다.

2. 문제풀이

2.1. 코드 설명하기

// input 문자열을 받아서 delim 글자로 구분한 뒤 vector<string>을 반환합니다.
#include <sstream>		// stringstream 또는 istringstram 클래스를 사용하기 위해 include합니다.
vector<string> split(const string& input, char delim) {
    vector<string> ret;
    string temp;
    stringstream ss(input);
    // input 문자열을 스트림에 넣은 뒤 delim 문자로 구분해서 temp에 저장한 뒤 vector에 넣습니다.
    while (getline(ss, temp, delim)) ret.push_back(temp);
    return ret;
} 

• 문자열 input을 delim문자를 기준으로 잘라서 문자열 배열에 저장하는 함수입니다.
• <sstream> 헤더를 포함해야하고 stringstream 인스턴스를 input으로 초기화합니다.
• getline() 함수를 이용해서 임시공간 temp에 자른 문자열을 배열에 저장한 뒤 반환합니다.
• 공식처럼 알아두면 편리합니다.

unordered_map<string, string> userDB;
vector<pair<string, string>> requestDB;

for (const auto& rec : record) {
    vector<string> command = split(rec, ' ');
    if (command[0] != "Leave") userDB[command[1]] = command[2];
    requestDB.push_back({command[0], command[1]});
}

• 유저 아이디를 key로 하고 닉네임을 value로 하는 unordered_map인 userDB를 만듭니다.
• 명령과 유저 아이디를 저장할 requestDB를 만듭니다.
  • map을 사용하지 않은 이유는 random access iterator를 지원하는 자료구조를 사용해야 입력 순서를 보존할 수 있기 때문입니다.
• record 속 모든 문자열을 위에서 만든 함수에 넣어 명령 = command[0], 유저 아이디 = command[1], 닉네임 = command[2]으로 분리합니다.
• 분리한 문자열을 각 용도에 맞게 userDB 또는 requestDB에 저장합니다.
• 이때 명령이 Leave인 경우, 닉네임인 command[2]가 존재하지 않으므로 segmentation fault 오류를 주의합시다.

2.2. 시간/공간복잡도 계산하기

• record 속 모든 문자열을 한 번씩 탐색하므로 $O(n)$ 입니다.

2.3. 전체코드

#include <vector>
#include <sstream>
#include <unordered_map>
using namespace std;

vector<string> split(const string& input, char delim) {
    vector<string> ret;
    string temp;
    stringstream ss(input);
    while (getline(ss, temp, delim)) ret.push_back(temp);
    return ret;
}

vector<string> solution(vector<string> record) {
    unordered_map<string, string> userDB;
    vector<pair<string, string>> requestDB;
    
    for (const auto& rec : record) {
        vector<string> command = split(rec, ' ');
        if (command[0] != "Leave") userDB[command[1]] = command[2];
        requestDB.push_back({command[0], command[1]});
    }
    vector<string> answer;
    for (const auto& req : requestDB) {
        if (req.first == "Change") continue;
        string ans = userDB[req.second] + "님이 ";
        ans += (req.first == "Enter") ? "들어왔습니다." : "나갔습니다.";
        answer.push_back(ans);
   }
    return answer;
}