Silver IV 난이도 문제를 C++로 풀이한 내용입니다. 채팅 기록에서 곰곰이가 인사를 하는 횟수를 계산하는 문제입니다.

백준 25192: 인사성 밝은 곰곰이

Silver IV 난이도 문제를 C++로 풀이한 내용입니다. 채팅 기록에서 곰곰이가 인사를 하는 횟수를 계산하는 문제입니다.

문제 소개

문제 번호: 25192
문제명: 인사성 밝은 곰곰이
난이도 (티어): Silver IV
사용 언어: C++
실행 시간: 928 ms
메모리: 8312 KB
문제 요약:
주어진 채팅 로그에서 곰곰이가 인사를 하는 총 횟수를 계산해야 합니다. 로그에는 일반적인 메시지와 "ENTER"라는 특별한 메시지가 포함됩니다. "ENTER" 메시지는 새로운 사람이 채팅방에 들어왔음을 나타냅니다. 곰곰이는 새로운 사람이 들어올 때마다 인사를 하며, 같은 사람이 여러 번 들어와도 한 번만 인사를 합니다. 즉, 각 사람이 처음 들어올 때 곰곰이는 한 번의 인사를 합니다.

접근 방법

문제를 해결하기 위해 각 사람이 처음 입장했을 때만 곰곰이가 인사를 한다는 점에 주목했습니다. 이는 결국 '고유한' 사람들의 수를 세는 것과 같습니다. 하지만 "ENTER" 메시지가 나올 때마다 새로운 그룹이 시작된다고 볼 수 있으므로, 각 "ENTER" 이벤트 이후에 등장하는 새로운 사람들의 수를 별도로 세어야 합니다.

이를 위해 std::unordered_set 자료구조를 사용했습니다. unordered_set은 중복을 허용하지 않으며, 요소를 삽입할 때 해당 요소가 이미 존재하는지 여부를 효율적으로 확인할 수 있습니다.

unordered_set<string> gomgom;: 채팅에 참여한 사람들의 이름을 저장할 집합입니다. 중복된 이름은 자동으로 제거됩니다.
int total_greetings = 0;: 곰곰이가 하는 총 인사 횟수를 저장할 변수입니다.
cin >> N;: 전체 채팅 기록의 줄 수를 입력받습니다.
while (N--) { ... }: 입력받은 줄 수만큼 반복하며 각 줄의 내용을 처리합니다.
cin >> input;: 현재 줄의 내용을 읽어 input 문자열에 저장합니다.
if (input == "ENTER") { gomgom.clear(); }: 만약 현재 줄이 "ENTER"라면, 이는 새로운 그룹이 시작되었음을 의미합니다. 따라서 gomgom 집합을 비워 이전 그룹의 사람들은 더 이상 고려하지 않도록 합니다.
else { if (gomgom.insert(input).second) { total_greetings++; } }: "ENTER"가 아니라면, 현재 input은 사람의 이름입니다. gomgom.insert(input)를 호출하여 집합에 이름을 삽입합니다. insert 함수의 반환값은 std::pair이며, second 멤버가 true이면 해당 요소가 집합에 새롭게 삽입되었다는 것을 의미합니다. 즉, 이전에 등장하지 않았던 새로운 사람이라는 뜻이므로, total_greetings를 1 증가시킵니다.

이 방식을 통해 "ENTER" 메시지를 기준으로 새로운 그룹이 시작될 때마다 unordered_set을 초기화하고, 각 그룹 내에서 처음 등장하는 사람의 수만큼만 인사 횟수를 증가시켜 정확하게 전체 인사 횟수를 계산할 수 있습니다.

풀이 과정

입출력 최적화: C++에서 대량의 입출력을 처리할 때는 ios_base::sync_with_stdio(false);와 cin.tie(NULL);를 사용하여 입출력 속도를 최적화하는 것이 중요합니다. 특히 이 문제는 시간 초과를 방지하기 위해 필수적입니다.
데이터 구조 선택: 채팅 참여자의 고유한 이름을 저장하기 위해 std::unordered_set<string>을 사용합니다. unordered_set은 평균적으로 O(1)의 시간 복잡도로 삽입, 삭제, 탐색이 가능하여 효율적입니다.
변수 초기화: 총 인사 횟수를 저장할 total_greetings 변수를 0으로 초기화합니다.
입력 처리 루프: 총 줄 수 N만큼 반복하는 루프를 시작합니다.
"ENTER" 메시지 처리: 루프 안에서 입력받은 문자열이 "ENTER"인지 확인합니다. 만약 "ENTER"라면, 새로운 채팅 그룹이 시작되었으므로 gomgom 집합을 clear()하여 비웁니다.
이름 삽입 및 카운팅: "ENTER"가 아니라면, 해당 문자열을 gomgom 집합에 삽입합니다. unordered_set::insert 메소드는 삽입 시 성공 여부를 pair 형태로 반환하는데, pair.second가 true이면 해당 요소가 집합에 새롭게 추가된 것입니다. 즉, 이전에 등장하지 않았던 새로운 사람입니다. 이 경우 total_greetings를 1 증가시킵니다.
결과 출력: 모든 줄의 처리가 끝나면 total_greetings 값을 출력합니다.

코드 설명

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main() {
    // 1. 입출력 속도 최적화 (이 부분이 없으면 시간 초과 가능성이 높음)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    // N 값을 입력받습니다. 입력 실패 시 프로그램 종료 (혹시 모를 예외 처리)
    if (!(cin >> N)) return 0;

    // 채팅에 참여한 고유한 사람들의 이름을 저장할 unordered_set
    unordered_set<string> gomgom;
    // 곰곰이가 하는 총 인사 횟수를 저장할 변수
    int total_greetings = 0;
    // 각 줄의 입력을 저장할 문자열 변수
    string input;

    // N번 반복하며 채팅 로그를 처리합니다.
    while (N--) {
        cin >> input; // 한 줄(단어)을 입력받습니다.

        // 현재 입력이 "ENTER"인지 확인합니다.
        if (input == "ENTER") {
            // "ENTER"가 들어오면 새로운 그룹이 시작되었으므로,
            // 이전 그룹의 사람들은 더 이상 고려하지 않기 위해 셋을 비웁니다.
            gomgom.clear();
        } else {
            // "ENTER"가 아니라면, 사람의 이름입니다.
            // gomgom.insert(input)는 pair<iterator, bool>을 반환합니다.
            // .second는 새로 삽입되었을 때만 true를 반환합니다.
            // 즉, 이전에 셋에 없었던 새로운 사람이라면 true를 반환하며,
            // 이 때 total_greetings를 1 증가시킵니다.
            if (gomgom.insert(input).second) {
                total_greetings++;
            }
        }
    }

    // 최종적으로 계산된 총 인사 횟수를 출력합니다.
    cout << total_greetings << "\n";

    return 0;
}

복잡도 분석

시간 복잡도:
- 입력을 N개의 문자열이라고 할 때, 각 문자열의 길이를 L이라고 가정합니다.
- unordered_set의 삽입(insert) 연산은 평균적으로 O(1)입니다. 최악의 경우 O(N)이 될 수 있지만, 해시 충돌이 적도록 잘 구현되어 있다면 평균적인 성능을 기대할 수 있습니다.
- unordered_set의 clear() 연산은 O(k)로, 여기서 k는 집합에 저장된 요소의 수입니다.
- 각 줄에 대해 cin >> input 연산은 문자열 길이에 비례합니다.
- 최악의 경우, 모든 사람이 "ENTER" 없이 계속 등장한다면 unordered_set에 N개의 요소가 저장될 수 있으며, 각 삽입은 O(1)입니다. 총 N번의 삽입이 이루어지므로 O(N).
- "ENTER"가 자주 등장하면 gomgom.clear()가 호출됩니다. clear()의 시간 복잡도는 집합의 크기에 비례합니다.
- 전체적으로, 입력 문자열의 총 길이를 S라고 할 때, unordered_set의 평균적인 삽입/탐색 성능을 고려하면 시간 복잡도는 대략 O(S) 또는 O(N * L_avg) (평균 문자열 길이)에 가깝습니다. 입력의 총 크기가 시간 복잡도를 결정한다고 볼 수 있습니다.
공간 복잡도:
- unordered_set에 저장되는 사람 이름의 최대 개수에 따라 공간이 결정됩니다.
- 가장 많은 사람이 동시에 unordered_set에 저장될 수 있는 경우는 "ENTER"가 한 번도 나오지 않거나 마지막에 나올 때입니다.
- 따라서 공간 복잡도는 unordered_set에 저장될 수 있는 최대 고유한 이름의 개수에 각 이름의 길이까지 고려해야 하므로, O(M * L_avg) 입니다. 여기서 M은 최대 고유한 사용자 수, L_avg는 평균 사용자 이름 길이입니다.

배운 점

이 문제를 통해 std::unordered_set의 유용성을 다시 한번 확인할 수 있었습니다. 특히 insert 메소드가 반환하는 pair의 second 값을 활용하여 요소가 새롭게 추가되었는지 여부를 효율적으로 판단하는 방법을 배웠습니다. 이는 중복을 제거하면서 특정 이벤트 발생 횟수를 세는 경우에 매우 유용합니다.

또한, C++에서 백준 알고리즘 문제를 풀 때 입출력 최적화(ios_base::sync_with_stdio(false); cin.tie(NULL);)가 시간 초과를 방지하는 데 얼마나 중요한지 체감할 수 있었습니다. 이 습관을 꾸준히 들이는 것이 중요하다고 생각합니다.

이 문제는 "고유한 요소의 개수를 세는 문제"에서 unordered_set을 어떻게 활용할 수 있는지, 그리고 "그룹" 또는 "구간"의 개념을 clear() 연산을 통해 어떻게 처리할 수 있는지를 명확하게 보여주는 좋은 예시입니다.