[2019 카카오 블라인드 채용 코딩테스트] 오픈채팅방 C++ 풀이 및 정답 코드

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42888

프로그래머스

 

 

 

문제 설명

문제가 길어서 겁먹을 수 있지만(내가 겁먹음) 실패율보다 쉬운 문제이다.
코딩테스트 당시 정답률은 실패율(55.57%)보다 약간 높은 59.91%이라고 한다.

주어진 string을 명령문으로 생각하면 첫번째 단어로 동작을 분기해서 각 동작을 처리해주면 된다.

 

 

 

문제 풀이

변하지 않는 아이디라고하면 생각나야하는게 있다. map이다.
닉네임을 골백번 바꿔도 아이디는 변하지 않으므로 아이디를 key로, 닉네임을 value로 같은 unordered_map을 사용하면 편할 것 같다.

닉네임 변천사를 저장하고 업데이트해주도록 unordered_map nicknames를 만들고 업데이트 한 후, 메세지를 만들도록 한번 더 포문을 돌아 메세지 배열을 만들어주면 된다.

저는 그저 편의를 위해 명령문 string의 단어 각각을 저장하는 records string 2D 배열을 만들었습니다.

 

 

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>

using namespace std;

vector<string> solution(vector<string> record) {
    vector<string> answer;
    unordered_map<string, string> nicknames;
    vector<vector<string>> records(record.size());
    
    for (int i=0; i<record.size(); i++) {
        stringstream ss(record[i]);
        string word;
        
        while(ss >> word)
            records[i].push_back(word);
    }
    
    for (auto r : records) {
        if (r[0] == "Enter" || r[0] == "Change") {
            nicknames[r[1]] = r[2];   
        }    
    }
    
    for (auto r : records) {
        if (r[0] == "Enter") {
            answer.push_back(nicknames[r[1]] + "님이 들어왔습니다.");
        } else if (r[0] == "Leave") {
            answer.push_back(nicknames[r[1]] + "님이 나갔습니다.");
        }      
    }
    
    return answer;
}

 

 

 

시공간 복잡도

*n을 문자열 배열 record의 크기라고 할 때

시간 복잡도: O(n)

공간 복잡도: ???
이거 생각해봤는데... c++ string vector 메모리 할당 방식에 따라 갈릴 것 같다.
런타임에 동적으로 할당해서 1D string vector를 2D string vector로 바꾸더라도 유의미한 메모리 할당은 늘어나지 않을지, 아니면 정적 사이즈를 할당하고 필요시 늘리는 방식인지 궁금하다.
전자이면 O(n)일 것이고 후자이면 O(M*W)일 것이다. 
조만간 찾아보고 글 쓰겠음

 

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰

어렵지 않았지만 좀 열받는 점은 테스트 케이스 추가하기가 어렵다는 거였다.
매칭 점수 문제도 그렇고, 실제 코딩테스트를 볼 때 히든 테케 통과하는지도 불확실한데 테케 추가하는것까지 한나절이면 속터질 것 같다.

문제 좀 배려있게 매너잇게 내주세요