[BOJ] 7785번: 회사에 있는 사람

https://www.acmicpc.net/problem/7785

2018.11.17 1차시도 - 시간초과

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

const size_t size{26};

vector<vector<string> > log;

unsigned int n;

cin >> n;

while (n--)

{

string name, condition;

cin >> name >> condition;

int point = name[0] - 65;

if (!(0 <= point && point < 91))

{

point = point - 32;

}

if (condition == "enter")

{

log[point].push_back(name);

}

else

{

vector<string>::iterator iter = find(log[point].begin(), log[point].end(), name);

if (iter != log[point].end())

{

log[point].erase(iter);

}

}

}

for (int i = 0; i < 26; i++)

{

sort(log[i].begin(), log[i].end());

}

for (int i = 0; i < 26; i++)

{

while (log[i].size())

{

cout << log[i].back() << endl;

log[i].pop_back();

}

}

return 0;

}

애초에 106개의 기록이 주어진다는 것과 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력해야 한다는 점에서 sort()를 쓰면 시간 초과가 나지 않을까 싶어서 나름 고민한다고 고민해서 vector로 2차원 배열을 만들어서 첫 번째 글자를 통해 A~Z까지 나눈 다음 2차원...뭐라하지 어쨌든 거기에 이름을 나눠 담고 따로 정렬한 다음에 따로 출력하려고 했었다. 한 vector에 이름을 싹 다 넣으면 찾는데도 시간이 오래 걸릴 것이고, 정렬하는데도 시간이 오래 걸릴 것 같아서 나름 생각한 방법인데 글 쓰면서 생각해 보니까 도긴개긴이라는 말이 떠오른다. 

---

C++ 이차원 배열 생성 방법

    vector > 식별자이름;

    > > 여기 사이에 빈칸이 굉장히 중요하다. 빈칸 없이 >>라고 하면 컴파일러가 shift연산자로 인식해서 컴파일시 에러를 출력한다.

C++ 벡터 내의 원소 찾는 방법

    iterator 사용, 의 find()사용

     vector::iterator iter = find(log[point].begin(), log[point].end(), name);
    
    만약, 원하는 벡터에서 원하는 값을 찾지 못한 경우, iter에는 구간의 끝값(.end())값이 저장된다.

    읭 그럼 만약 구간의 끝값이 찾는 값이면 어떡하지?

이용해서 역순 정렬하기

    #include 하면 greater<자료형>() 함수가 있는데, 이걸 sort할때
    sort(처음, 끝, greater()); 이렇게 쓰면 손 쉽게 역순 정렬을 할 수 있다.

vector.pop_back()과 vector.back()

    vector.pop_back() -> pop해서 없애버림
    vector.back() -> 맨 끝 값 return