[백준 25192] 인사성 밝은 곰곰이

문제

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

25192번: 인사성 밝은 곰곰이

 

 

문제 분석

우선 몇 가지의 입력이 있을지 입력 받고, 

 

그 이후 문자열이 들어온다. 

 

문자열이 이전에 들어오지 않은 문자열이라면 값을 하나 올린다. 

다만 'Enter'가 들어오면 전에 입력 받은 값들이 초기화 된다. 

 

그렇게 올린 값을 출력하는 문제이다. 

 

 

알고리즘 설계

우선 입력 받을 값과, 출력할 값을 담을 정수형 변수, 

입력 받고 확인할 문자열, 

앞에서 입력 받은 문자열인지 확인하는 set 이렇게 선언 해준다. 

 

몇개의 문자열이 들어올지 입력 받고 반복문을 돌려준다. 

 

반복문 안에서 문자열을 입력 받고, 

 

만약 입력 받은 문자열이 "Enter"라면 set의 size를 출력값에 더해주고, set을 초기화 해준다. 

다른 값이 입력 받았다면 set에 추가해준다. 

 

이후 출력하면 된다. 

 

 

유의점

본 문제는 unordered_set을 사용하면 시간초과가 나는 문제이다.

 

unordered_set에 find함수를 사용할때 해쉬 충돌이 많이 나는 경우 O(n)까지 늘어나기에 set이 더욱 빠르다. 

 

 

코드

#include <iostream>
#include <set>

using namespace std;

int main()
{
    int input, answer = 0;
    string str;
    set<string> s;
    cin >> input;

    while (input--)
    {
        cin >> str;
        if (str == "ENTER")
        {
            answer += s.size();
            s.clear();
        }
        else
        {
            if (s.find(str) == s.end())
                s.insert(str);
        }
    }

    cout << answer + s.size();
}