[백준(BOJ)] 25192번 인사성 밝은 곰곰이 C++

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

25192번: 인사성 밝은 곰곰이

 

 

어떤 문제인가?

채팅방에 새로운 사람이 들어왔을 때 유저의 닉네임의 첫 번째 등장만이 신입에게 인사를 한 채팅이다.

그 외의 나머지는 잡답이다.

따라서 ENTER가 입력된 후에 처음 등장한 닉네임의 숫자만 세주면 된다.

 

 

접근 방법

문제를 읽자마자 map을 써야겠다고 생각했다.

map<string, bool> user;

유저의 이름을 key로 인사 여부를 value로 저장하는 map을 선언했다.

 

int N;
string s;
int cnt = 0;

cin >> N;

문제에서 주어진 변수들을 선언하고 입력받는다.

 

 

for (int i = 0; i < N; i++) {
    cin >> s;
    if (s == "ENTER") {
        user.erase(user.begin(), user.end());
    } else {
        if (!user[s]) {
            cnt++;
            user[s] = true;
        }
    }
}

만약 입력이 ENTER라면 기존에 map에 존재하는 원소들을 다 지워버린다.

 

그 외에 유저의 닉네임이 입력됐을 때는 key(유저의 닉네임)에 대한 value(인사 여부)를 확인한다.

value가 false라면 아직 인사를 하지 않은 유저이니 cnt를 증가시켜주고, value를 true로 바꿔준다.

 

cout << cnt;

for문을 끝낸 후 cnt를 출력해주면 끝!!

 

 

무엇이 어려웠는가?

map을 사용할 줄 안다면 아주 쉽게 풀리는 문제라 어려운 부분이 없었다.

 

 

시간 복잡도

내 풀이 같은 경우에는 먼저 for문을 n번만큼 반복한다.

그 안에서 vector의 삭제 연산이 발생하는 경우가 존재한다.

최악의 경우 -> 첫 입력과 마지막 입력을 제외한 모든 입력 동안 새로운 유저의 닉네임만 입력된다.

그렇다면 첫 입력과 마지막 입력인 ENTER를 제외하고 n-2크기 만큼의 map이 된다.

이 map을 지우는데 O(n)시간이 걸린다.

 

따라서 시간복잡도는 O(n^2)이 된다.