정답
- 핵심은
set과 역순 출력하는 방법 알아두기~- rbegin(), rend() 면 역순이다.
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
//이름이 있다는 건 이미 enter했다는 것
//set 사용
int main()
{
int n;
cin >> n;
set<string> s; //자동 정렬, 자동 중복 제거
for(int i=0; i<n; i++){
string name, record;
cin >> name >> record;
if(record == "enter") s.insert(name);
else s.erase(name);
}
for(auto i = s.rbegin(); i != s.rend(); i++){
cout << *i << "\n";
}
return 0;
}생각의 흐름
벡터를 하나 만들고.
enter -> 추가 push_back
leave -> 제거?
제거가 메인인 문제에서 과연 vector는 좋은 선택인가?
vector에서 원소 하나를 삭제하는 시간복잡도는 O(N)
pair<string, bool>을 사용해서 마지막에 true인 친구들만 sort해서 출력하는 방법.
찾아서 삭제하나... 찾아서 변경하나.... 얘도 시간 복잡도가 비슷할 것 같음
그럼 일단 pair로 가보자. 이게 더 깔끔해보임!
=> 시간 초과
그럼.........
이름이 이미 존재한다는 건 enter 했다는 거 아닌가?
있으면 remove, 없으면 추가?
위랑 다를 게 뭔데..........
정답을 봤다!
set을 이용하여 출퇴근 하는 사람들을 관리하는 게 핵심
첫번째 시도 -> 시간 초과
pair<이름, 출입기록> 넣고 마지막에 출입기록이 enter인 사람을 sort해서 출력했다.
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(string a, string b){
return a > b;
}
int main()
{
int n;
vector<pair<string, bool>> v;
vector<string> answer;
cin >> n;
for(int i=0; i<n; i++){
string name, record;
cin >> name >> record;
if(record == "enter"){
v.push_back(make_pair(name, true));
}
else{ //leave
for(int j=0; j<v.size(); j++){
if(v[j].first == name) v[j].second = false;
}
}
}
for(int i=0; i<v.size(); i++){
if(v[i].second){
answer.push_back(v[i].first);
}
}
sort(answer.begin(), answer.end(), compare);
for(int i=0; i<answer.size(); i++){
cout << answer[i] << "\n";
}
return 0;
}두 번째 시도 -> 시간 초과
leave -> vector.erase 사용했다. 장렬하게 시간 초과.
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool compare(pair<string, bool> a, pair<string, bool> b){
return a.first > b.first;
}
int main()
{
int n;
vector<pair<string, bool>> v;
vector<string> answer;
cin >> n;
for(int i=0; i<n; i++){
string name, record;
cin >> name >> record;
if(record == "enter"){
v.push_back(make_pair(name, true));
}
else{ //leave
for(int j=0; j<v.size(); j++){
if(v[j].first == name) v.erase(v.begin()+j);
}
}
}
sort(v.begin(), v.end(), compare);
for(int i=0; i<v.size(); i++){
cout << v[i].first << "\n";
}
return 0;
}3번째 시도 -> 틀렸습니다.
set을 사용했다.
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
//이름이 있다는 건 이미 enter했다는 것
//set 사용
int main()
{
int n;
cin >> n;
set<string> s; //자동 정렬, 자동 중복 제거
for(int i=0; i<n; i++){
string name, record;
cin >> name >> record;
if(record == "enter") s.insert(name);
else s.erase(s.find(name));
}
for(auto i : s) cout << i << "\n";
return 0;
}역순 출력 안 한 거였음. 바보인가?
기억할 것
- v.erase()
v[5]를 지우고 싶다면
v.erase(v.begin() + 5);
sort는 앞에 v. 이 안 붙지만 erase()는 붙는다.
그리고 iterator가 &로 들어가는 게 아니라 begin()에서 +i 들어감! - set
- 숫자든 문자든 중복을 없엔다.
- 삽입하는 순서에 상관없이 정렬되서 입력이 된다.
왜? 이진트리니깐,,
당장 기억해야할 사용법은 아래와 같다. (매우 주관적인 판단)
- set<자료형> 변수 : 기본적인 선언방법
- s.insert() : s에 값 삽입
- s.erase(
값/주소값) : s에 저장된 요소 삭제. 주소값 말고 해당 값이 들어가도 됨!!- s.swap() : s1과 s2를 서로 교환
- s.begin() : set의 시작이 되는 주소 값 반환
- s.end() : set의 마지막 부분에 대한 주소 값 반환(정확히는 마지막 뒤 공백구간)
- s.size() : s에 저장되어 있는 크기
- s.find(찾을 값) : 찾기 ex) s.find(1) -> 해당 자리 주소값 반환
-> s.erase(s.find(1)) 이런 식으로 사용 가능!
insert로 값 삽입하는 것 빼곤 vector랑 비슷함
set<pair<int, int>> 이렇게 사용 가능한 것도 기억해두자!
의외로 출력하는 데 애 먹음;ㅎ
// 출력
for(auto i : s){
cout << i;
}
// 리버스 출력
for (auto iter = s.rbegin(); iter != s.rend(); iter++) {
cout << *iter << '\n';
}참고
C++ 벡터 특정 원소 지우는 방법 vector.erase(),remove() 등 Tips
C++ set 사용법과 설명
