[프로그래머스] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) / C++

euneun·2021년 5월 25일
1

알고리즘

목록 보기
1/12

프로그래머스 오픈채팅방
https://programmers.co.kr/learn/courses/30/lessons/42888
문제 내용이 길어서 내용은 생략합니다.

문제풀이 과정

  1. 사용자 정보를 저장할 자료구조와 나가고 들어간 정보를 저장할 자료구조 선언
unorderd_map <string,string> user_info;

vector <pair<char,string>> v;
  • 유저정보는 uid가 key가 되게 하고, 닉네임은 계속 변경되므로 value가 되게 하여 해시맵에 저장한다.
    -> 이 정보는 정렬될 필요가 없으므로 unordred_map을 이용한다.

  • 들어오고 나간 정보는 ('E','uid1234') 와 같이 쌍으로 저장해서 순서대로 삽입하기 쉬운 vector를 만든다.

  1. 문자열 분해하는 함수 구현
["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"]

이렇게 입력으로 들어온 record배열에서 Enter/uid1234/Muzi
들어온정보/유저아이디/이름 으로 분리시켜줄 수 있는 record[i]에 해당하는 string을 나누어주는 함수가 필요하다.

record[i]의 첫글자가 E일 경우, Enter는 5글자이므로, 6번째부터 record[i]의 분해를 시작한다.
' '를 만나기 전까지, 문자 하나하나를 temp에 덧붙여가다가 ' '(space)를 만나면 temp를 return해준다.
index의 주소값 (int& i)을 받아오므로, 함수내에서 i++하게 되면 index값또한 변경되게끔 한다.


string token_string(const string s, int& i){
    string temp = "";
    for( ; i < s.size(); i++){
        if(s[i] == ' '){ i++; return temp; }
        temp += s[i];
    }
    return temp;
}

if(record[i][0] == 'E'){
            int index = 6;
            uid = token_string(record[i], index); //uid1234 저장
            nickname = token_string(record[i], index); //Muzi 저장
            ...
            }
            ...

참고 : c++ 자료구조 - vector , unordered_map

vector

vector의 push_back()emplace_back()의 성능상 차이점은?

둘다 vector의 끝에 원소를 추가하는 함수이다.

  • push_back
    삽입할 객체를 받아 임시 객체를 만들고 push_back 내부에서 복사가 일어난 뒤 vector에 추가 한다.
  • emplace_back
    삽입할 객체의 생성자를 위한 인자들을 받아 함수 내부에서 직접 객체를 생성하여 삽입하므로 임시 객체의 생성과 파괴, 복사(혹은 move)등을 하지 않아도 되어 성능상 유리하다.

원래 push_back만 써왔었는데, 이문제를 통해 emplace_back이라는 함수를 알게되어 공유해본다.

자세히 알아보고싶다면, 아래 블로그 링크에 자세히 설명되어있다!
https://m.blog.naver.com/sorkelf/220825930008

unordered_map

unordered_map (== 해시맵) 자료구조 사용이유

unordered_map은 순서도 없고, 중복도 허용하지않는 (key, value) 쌍의 값을 저장하는 자료구조이다.
map과 비교하여 자동으로 정렬하지 않고 저장하기 때문에, 시간복잡도 O(1)이라는 좋은 성능을 가지고 있어, 따라서 이렇게 순서와 상관없이 값을 저장할 경우에는 성능면에서 unordered_map을 사용하는 것이 좋은 것 같다.

unordered_map 기본 사용법

우선 #include <unordered_map> 을 헤더에 포함시켜 주어야 한다.

  • 선언
unordered_map<int,string> u;
: key가 int형이고, value가 string형인 unordered_map u를 선언함
  • 삽입
u[1]=dog; 
: u에 키가 1이고, 값이 dog인 쌍을 넣어준다.

🔮 기존의 키값이 존재하면, 값을 덮어씌운다 !!!🔮
map을 사용하는 이유! 이 문제와 일맥상통한다

  • 삭제
u.erase(1);
키값 1에 해당하는 원소를 삭제
  • 검색
i=u.find(1);
key값 1에 해당하는 원소의 iterator를 반환한다.
없으면, u.end() iterator를 반환한다.

없을경우,

u.find(1)==u.end(); // true

🔮 unordered_map에 대한 iterator는 pair이다. 🔮
따라서, iterator.first를 조회하고, iterator.second을 조회한다.

u.count(1);
 key에 해당하는 value의 개수를 반환

-> 보통 key가 존재하는지 확인하는데 사용한다.


전체 코드

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

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

string token_string(const string s, int& i){
    string temp = "";
    for( ; i < s.size(); i++){
        if(s[i] == ' '){ i++; return temp; }
        temp += s[i];
    }
    return temp;
}

vector<string> solution(vector<string> record) {
    unordered_map<string, string> m;
    vector<pair<char, string> > v;
    vector<string> answer;

    for(int i = 0; i < record.size(); i++){
        string uid = "";  string nickname = "";
        if(record[i][0] == 'E'){
            int index = 6;
            uid = token_string(record[i], index);
            nickname = token_string(record[i], index);
            v.emplace_back(make_pair('E', uid));
            m[uid] = nickname;
        }else if(record[i][0] == 'L'){
            int index = 6;
            uid = token_string(record[i], index);
            v.emplace_back(make_pair('L', uid));
        }else{
            int index = 7;
            uid = token_string(record[i], index);
            nickname = token_string(record[i], index);
            m[uid] = nickname;
        }
    }

    for(int i = 0; i < v.size(); i++){
        string temp = "";
        if(v[i].first == 'E')
            temp = m[v[i].second] + "님이 들어왔습니다.";
        else
            temp = m[v[i].second] + "님이 나갔습니다.";
        answer.emplace_back(temp);
    }

    return answer;
}

테케 왕많다...!@

어떤 자료구조를 생각할지만 떠올리면 별로 어렵지 않은 문제

끝 😊

profile
제대로 짚고 넘어가자!🧐

0개의 댓글