[백준(BOJ)] 7785번 회사에 있는 사람 C++

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

7785번: 회사에 있는 사람

어떤 문제인가?

n번 입력을 받고 사람의 이름에 대해 출근, 퇴근을 처리한다.

입력이 끝난 후 퇴근하지 않은 사람들의 이름을 역순으로 출력한다.

문제의 요구사항은 어렵게 느껴지지 않았다.

 

 

접근 방법

vector<string> people;
for(int i=0; i<n;i++){
    string name, enter;
    cin >> name >> enter;
    if(enter=="enter"){
        people.push_back(name);
    }
    else if(enter =="leave"){
        people.erase(remove(people.begin(),people.end(),name), people.end());
    }
}

처음에는 벡터를 사용해서 사람들의 이름을 추가하고 삭제하는 방법을 선택했다.

enter가 입력되면 벡터에 이름을 추가하고, leave가 입력되면 벡터에서 이름을 삭제했다.

출력을 정상적이었지만 시간 초과가 떴다.

leave가 입력됐을 때 erase, remove함수를 실행하는 과정에서 시간 초과가 발생한 것 같았다.

 

 

그래서 map을 사용하기로 했다.

map<string, bool> people;
for(int i=0; i<n;i++){
    string name, enter;
    cin >> name >> enter;
    if(enter=="enter"){
        people[name]= true;
    }
    else if(enter =="leave"){
       people[name]= false;
    }
}

map을 사용해서 아주 쉽게 구현할 수 있었다.

 

입력이 모두 끝난 다음 퇴근하지 않은 사람만을 출력해야한다.

vector<string> enterPeople;
for(auto iter = people.begin() ; iter != people.end(); iter++){
    if(iter->second){
       enterPeople.push_back(iter->first);
    }
}

 

따라서 퇴근하지 않은 사람들의 이름을 저장할 vector를 선언했다. 그리고 map을 순회하며 만약 iter->second(회사에 사람 존재 유무)가 true이면 vector에 iter->first(이름)을 추가했다.

 

이제 출력을 해야한다. 문제의 조건이 이름의 역순으로 출력이기 때문에 vector를 이름의 역순으로 정렬해줄 compare함수를 선언한다.

bool compare(string a, string b){
    return a>b;
}

 

 

그 다음 vector를 정렬해준다.

sort(enterPeople.begin(), enterPeople.end(), compare);

이렇게 되면 퇴근하지 않은 사람들의 이름이 역순으로 정렬되어있을 것이다.

 

이제 이 vector의 원소들을 차례대로 출력해주기만 하면 끝이다!

for(string name : enterPeople){
    cout << name << "\n";
}

 

배운 점

문제를 푸는 방식이 어렵진 않았지만 문제에서 원하는? 요구하는? 자료구조를 찾는 것이 정말 중요하다는 것을 배웠다.

문제를 풀기 전에 데이터를 저장할 자료구조를 빠르고 정확하게 판단하는 실력을 더 키워야겠다고 느꼈다.

 

 

시간 복잡도

일단 입력받은 n번만큼 출근 퇴근, 처리를 해야한다. -> O(N)

 

최악의 경우) 만약 퇴근없이 n번 모두 출근만한다면 map과 ,vector모두 크기가 n이 될 것이다.

이때 map, vector를 순회할 때 O(N)이 된다.

따라서 최악의 경우여도 O(N)이므로 시간 복잡도에 영향이 없다.