[백준] 7785번 회사에 있는 사람

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

 

오랜만에 문제푸는것 같다.

이제 부터 자료구조만 풀예정이다. ㅎㅎ

이 문제는 set이나 map으로 푸는 문제다. 웬지는 모르겠지만 부캠에서 이와 비슷한 문제가 나올것 만 같다.

1차때 set을 구현하는 문제가 나온것 처럼 이번에도 set을 사용하지 않고 푸는 것이 좋을 거라고 생각한다.

마치 1차는 연장선같은 느낌이라는 것 같다. 이쯤에서 그만 두고

본론인

문제부터 보면

처음에 이 문제를 접근했을때

이름이 존재하면 배열을 다시 돌려서 그 이름이 있는지 확인하고 빈 문자열로 바꿔주는 방법을 선택하였다.

#include <bits/stdc++.h>
 using namespace std;

pair<string,bool> ent[100000];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

  int n;
  cin >> n;

  for(int i = 0; i<n;i++) {
    string name, action;
    cin >> name >> action;

    ent[i].first = name;
    if (action == "enter") {
      ent[i].second = true;
    } else {
      ent[i].second = false;
    }
    
    //로그에 이름이 존재할 경우
    for(int j = 0; j<i;j++) {
      if (ent[i].first == ent[j].first) {
        ent[j].first = "";
      }
    }
  }

  sort(ent,ent+n);

  for(int i = n-1;i>-1;i--) {
    if (ent[i].first =="") continue;
    if (ent[i].second) {
    cout << ent[i].first << "\n";
    }
  }
 



}

 하지만 이렇게 작성한 코드는 100% 시간 오류가 발생한다.

왜냐하면 반복문이 2번돌기 때문이다. 결국 n^2의 시간이 걸린다는 건데... 이거는 10에 12승과 같은 숫자다

100,000,000,000 천억이다.  int가 21억이고 보통 1초동안 갈수 있는 범위가 10억 정도라고 알고 있다.

근데 이건 10억보다 100배정도 더 크다. 즉, 1초는 무조건 넘는다는 뜻이다.

시간제한도 1초이기 때문에 이렇게 풀면 답이 되지 않는다.

그래서 어떻게 풀지 고민하던 중

map을 쓰기로 결정했다. 하지만 곰곰히 생각해보니 굳이 map을 쓸 이유가 없었다.

왜냐하면 1가지 정보만 저장하면 되기 때문이다.

즉, 이름만 저장하면 되지 출입 여부는 저장할 필요는 없다고 생각했다.

그렇게 해서 두 번째 코드가

#include <bits/stdc++.h>
 using namespace std;

set<string> ent;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

  int n;
  cin >> n;

  for(int i = 0; i<n;i++) {
    string name, action;
    cin >> name >> action;

    bool flag;
    
    if (action == "enter") {
      flag = true;
    } else {
      flag = false;
    }

    if (flag) {
      ent.insert(name);
    } else {
      ent.erase(name);
    }
  }

  for(auto iter = ent.rbegin(); iter != ent.rend(); iter++) {
    cout << *iter << "\n";
  }
 



}

이런식으로 나왔다. 

이 코드에 쓸모없는 코드?가 있는데 그거는 flag를 선언하는 부분이다. 근데 굳이 추가한 이유는 순전히 가독성때문이다.

다른사람들은 잘 모르겠지만 나는 이방법이 더 이해하기 편했다.

enter 이라면 flag를 true로

leave라면 flag를 false라는 뜻이다.

 

true라면 값을 추가해주고

flase라면 그 이름을 제거해주는 방법을 선택했다.

그리고 나서 반복문을 돌리면 된다.

사실 반복문은 어떤 뜻인지 잘 모르겠다.

 set이라는게 자동으로 정렬이 되어있다고 한다. 그래서 정렬할 필요가 없다고 한다.

근데 문제에서 역순으로 출력하라고 했다.

인터넷에서 찾아보니

rbegin() 과 rend()가 역순을 뜻하는거라고 한다.

iter라는 값이 rend와 같아지는 순간 반복문은 종료된다. 

using namespace std;

map<string,string,greater<string> > list;

int main()
{
    int n;
    string name, state;
    cin >> n;
    while(n--){
        cin >> name >> state;
        list[name]=state;
    }
    map<string,string, greater<string> >::iterator iter;
    for (iter=list.begin();iter!=list.end();iter++){
        if(iter->second == "enter") cout << iter->first << '\n';
    }
    
}

 

근데 곰곰히 생각해보니 리스트로도 가능할 것 같다.

이따 자바로 다시 풀어봐야지 set,map금지인 상태에서 풀어봐야겠다.ㅎㅎ