[백준/C++] 7785(회사에 있는 사람) (문자열 비교 / Hash / unordered_map, unordered_set)

 

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

 

 

내가 해냄

#include <bits/stdc++.h>
// #include <unordered_map>    // 원래는 <bits/stdc++.h> 만 include해도 동작하는데 VS에서 동작하지 않아서 추가로 include
using namespace std;

long long n;    // 출입 기록 수
unordered_map <string, string> syslog; // 출입 기록 로그 (이름 - 출입 상태 저장)
vector<string> cur;   // 현재 회사에 있는 사람들 (정렬을 위해 사용)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // 출입 기록 수를 입력받는다
    cin >> n;

    // 출입 기록을 입력받는다
    for (int i = 0; i < n; i++)
    {
        string tmp1, tmp2;
        cin >> tmp1 >> tmp2;

        syslog[tmp1] = tmp2;  // 마지막 출입 상태만 저장됨 (enter / leave)
    }

    // 현재 회사에 있는 사람들을 기록한다
    // unordered_map을 순회하여 "enter" 상태인 사람만 벡터에 추가
    // *** string은 == 연산자 오버로딩이 되어 있어서 두 문자열이 같은지 비교 가능 ***
    for (auto i : syslog)
        if (i.second == "enter")
            cur.push_back(i.first);

    // 현재 회사에 있는 사람들을 역순으로 정렬한다
    // *** greater<string>()을 비교자로 전달하여 사전 역순(내림차순)으로 정렬한다 ***
    sort(cur.begin(), cur.end(), greater<string>());

    // 회사에 있는 사람들을 출력한다
    for (string i : cur)
        cout << i << '\n';

    return 0;
}

 

사용한 핵심 개념

// `unordered_map<string, string>` (해시 맵)

 

• 역할 : 사람의 이름(string)을 키(key)로 하고, 출입 상태("enter" 또는 "leave")를 값(value)으로 저장하는 자료구조다.
• 특징
  • 평균 O(1)의 시간 복잡도로 빠른 검색, 삽입, 삭제가 가능하다.
  • 마지막으로 기록된 출입 상태만 저장된다. (즉, 동일한 이름의 키가 등장하면 새로운 값으로 덮어씌워진다.)
• 사용 예시

unordered_map<string, string> syslog;
syslog["Alice"] = "enter";  // Alice가 회사에 들어옴
syslog["Alice"] = "leave";  // Alice가 퇴근 → 이전 값 "enter"가 덮어씌워짐

 

 

// `vector<string>`의 활용

• 역할 : 현재 회사에 남아 있는 사람들을 저장하고, 정렬 후 출력하는 역할을 한다.
• 사용 예시

vector<string> cur;

 

// `std::string`의 `==` 연산자 활용

• 역할: "enter"인지 "leave"인지 비교하여 현재 회사에 남아 있는 사람을 판별한다.
• 사용 코드

if (i.second == "enter")
    cur.push_back(i.first);

• 작동 원리:
  • C++의 `std::string` 클래스는 `==` 연산자가 오버로딩되어 있어 두 문자열이 같은지 쉽게 비교할 수 있다.
  • C 스타일 문자열(char*)과 다르게 직접 비교가 가능하며, `strcmp()`를 사용할 필요가 없다.
• 예제

string a = "hello";
string b = "hello";
string c = "world";

if (a == b) cout << "a와 b는 같다.\n";
if (a != c) cout << "a와 c는 다르다.\n";

• 출력 결과

a와 b는 같다.
a와 c는 다르다.

• 시간 복잡도: O(N) (두 문자열의 길이가 N일 경우)

 

cf) `std::string::compare()` 함수

• 역할: `std::string::compare()`는 문자열 비교 결과를 정수 값으로 반환한다.
• 사용 예시

string a = "apple";
string b = "banana";

if (a.compare(b) == 0) cout << "같다.\n";
else if (a.compare(b) < 0) cout << "a가 b보다 사전순으로 앞에 있다.\n";
else cout << "a가 b보다 사전순으로 뒤에 있다.\n";

• 출력 결과

a가 b보다 사전순으로 앞에 있다.

• 비교 결과 값:
  • 0 → 두 문자열이 같다.
  • < 0 → 첫 번째 문자열이 사전순으로 앞에 있다.
  • > 0 → 첫 번째 문자열이 사전순으로 뒤에 있다.

 

하지만 단순히 문자열이 같은지 비교할 때는 `==` 연산자를 사용하는 것이 더 직관적이고 간결하다.

 

// `sort()` + 비교 함수 `greater<string>()` (사전 역순 정렬)

• 역할: 회사에 남아 있는 사람들의 이름을 사전 역순(내림차순) 정렬하는 역할을 한다.
• 구현 방식:

sort(cur.begin(), cur.end(), greater<string>());

• 작동 원리:
  • 기본적으로 sort()는 오름차순 정렬을 수행한다.
  • `greater<string>()`을 비교 함수로 전달하면 내림차순 정렬을 수행하여 사전 역순으로 정렬된다.

• 사용 예시

vector<string> names = {"Alice", "Charlie", "Bob"};
sort(names.begin(), names.end(), greater<string>());
// 정렬 후: {"Charlie", "Bob", "Alice"} (사전 역순)

---

 

AI 피드백

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;  // 출입 기록 수
    cin >> n;

    unordered_set<string> syslog; // 현재 회사에 있는 사람들 저장

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

        if(action == "enter") syslog.insert(name);  // 입장 기록
        else syslog.erase(name);    // 퇴장 기록
    }
    
    // 출입 기록을 모두 처리한 후, 회사에 남아 있는 사람들을 벡터에 저장
    vector<string> cur(syslog.begin(), syslog.end());

    // 사전 역순(내림차순) 정렬
    sort(cur.begin(), cur.end(), greater<string>());

    // 결과 출력
    for (const string& name : cur)
        cout << name << '\n';

    return 0;
}

 

초기 코드 핵심 로직 분석

초기 코드에서는 `unordered_map<string, string>`을 사용하여 이름을 키(key), 출입 상태를 값(value) 으로 저장하는 방식으로 구현하였다. 마지막으로 기록된 출입 상태만 저장되므로, 동일한 이름이 여러 번 등장해도 최종 상태만 유지가 된다.
출입 기록을 받은 후 "enter" 상태인 사람들만 벡터에 추가한 후, 사전 역순(내림차순)으로 정렬하여 출력하였다.

unordered_map<string, string> syslog; // (이름, 출입 상태)

for (int i = 0; i < n; i++) {
    string name, action;
    cin >> name >> action;
    syslog[name] = action;  // 마지막 출입 상태만 저장됨
}

// 현재 회사에 있는 사람들을 벡터에 추가
for (auto i : syslog)
    if (i.second == "enter")
        cur.push_back(i.first);

// 내림차순 정렬 후 출력
sort(cur.begin(), cur.end(), greater<string>());
for (string i : cur)
    cout << i << '\n';

 

주요 개선점 :  `unordered_set<string>`의 사용

• 초기 코드는 unordered_map<string, string>을 사용하여 {"이름", "enter"} 혹은 {"이름", "leave"} 형태로 저장하고 있지만, 사실 "leave"를 저장할 필요는 없다.
• 대신 `unordered_set<string>`을 사용하면 더 간결하고 직관적이며, O(1)의 탐색 속도로 더 빠르게 동작할 수 있다.
• 해당 자료형을 사용함으로써 개선된 내용은 다음과 같다

기존 코드	개선된 코드
"leave" 상태를 따로 저장하여 비교	"leave" 상태를 저장하지 않고, `erase()`로 삭제
"enter" 상태를 벡터에 따로 저장	`unordered_set`에서 `vector`로 변환 후 정렬
벡터를 따로 관리하며 "enter" 상태만 저장	`unordered_set` 자체가 "enter" 상태인 사람만 저장

 

unordered_set<string> syslog; // 현재 회사에 있는 사람들 저장

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

    if (action == "enter") syslog.insert(name);  // 입장 기록
    else syslog.erase(name);  // 퇴장 기록
}

// 출입 기록을 모두 처리한 후, 벡터로 변환
vector<string> cur(syslog.begin(), syslog.end());

// 내림차순 정렬 후 출력
sort(cur.begin(), cur.end(), greater<string>());
for (const string& name : cur)
    cout << name << '\n';

 

추가로 사용한 개념

// unordered_map → unordered_set로 변경

• 기존 코드 문제점:
  • `unordered_map`을 사용하여 "enter"와 "leave" 값을 저장했으나, 사실 "leave" 상태는 따로 저장할 필요가 없다.
    • 회사를 떠난 사람은 최종 결과에서 출력하지 않기 때문이다.
• 개선 코드 장점:
  • "enter"일 때는 insert(), "leave"일 때는 `erase()`를 사용하여 바로 추가 및 삭제가 가능하다
  • 불필요한 "leave" 값 비교 연산을 제거하여 연산 속도가 평균 O(1)으로 개선된다

unordered_set<string> syslog;

if (action == "enter") syslog.insert(name);
else syslog.erase(name);

 

// 벡터 변환 후 정렬 (vector<string> cur(syslog.begin(), syslog.end());)

• 기존 코드 문제점:
  • "enter" 상태인 사람을 벡터에 따로 추가하는 과정이 필요했다
• 개선 코드 장점:
  • `unordered_set`을 벡터의 생성자로 변환하여 한 번에 저장할 수 있다.
  • `vector<string> cur(syslog.begin(), syslog.end());`를 사용하여 O(N) 시간 내 변환할 수 있다.

 

 

---

 

 

이분 탐색이나 투 포인터 방식을 이용하여 구현할 수도 있다고 한다