백준 16934 - 게임 닉네임 (C++)

문제

• 문제 링크

  
   BOJ 16934 - 게임 닉네임 
  

• 문제 요약

문제에 정의된 별칭 규칙에 따라 $N$명의 유저의 별칭을 찾아주자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N ≤ 100,000$

닉네임은 알파벳 소문자로만 이루어져 있고, 길이는 $10$을 넘지 않는다.

알고리즘 분류

• 자료 구조(data structures)
• 문자열(string)
• 해시를 사용한 집합과 맵(hash _ set / map)

풀이

굳이 트라이를 써먹지 않아도 해쉬 셋과 맵만으로 더욱 간단하고 효율적으로 풀이할 수 있다.

• 먼저 $N_i$번째 닉네임이 주어지면 $[1, 1], [1, 2], ... [1, n]$ 단위로 잘라보며 별칭이 될 수 있는지 확인한다.
• 만약 별칭이 될 수 있는 순간이 온다면 그 순간의 문자열을 출력해주자.
• 위 과정에서 추출되는 모든 문자열을 모아주자. 이들은 이후 문자열들의 별칭이 될 수 없다.
• 별칭을 찾지 못했다면 문제의 규칙에 따라 $N_i$ $+$ $count(N_i)$ 의 결과를 출력해주면 된다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
unordered_map <string, int> M;
unordered_set <string> S;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (string s, t; n--; cout << '\n')
    {
        bool f{};
        cin >> s; M[s]++;
        for (int i{}; i < s.size(); i++)
        {
            t = s.substr(0, i + 1);
            if (!f && !S.count(t))
                cout << t, f = 1;
            S.insert(t);
        }
        if (!f)
            M[s] == 1 ? S.insert(s), cout << s : cout << s + to_string(M[s]);
    }
}

comment

끝