[코드포스 Practice14] D. Secret Passwords

 

워...

신기한 발상....

 

알파벳 전부 포함해야해서 루트에 벡터 만들어서 알파벳 뭐 있는지 저장하는 걸 만들까 했는데 좋은 방법이 있었다. 

 

알파벳만 저장하는 저장하는 벡터를 만들어서

그 알파벳이 나온 집합의 번호를 저장한 다음에 그걸 merge 시킨다. 

 

글로 적으니 설명하기 어렵네 위의 사진을 보세용

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<int> parent;
vector<int> alphabet[26];

void    init(int n)
{
    parent.resize(n + 1);

    for (int i = 1 ; i <= n; i++)
        parent[i] = i;
}

int     find(int x)
{
    if (x == parent[x])
        return x;
        
    return (parent[x] = find(parent[x]));
}

void     merge(int x, int y)
{
    x = find(x);
    y = find(y);
    
    parent[x] = y;
}

int     main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++)
        {
            alphabet[s[j] - 'a'].push_back(i);
        }
    }
    init(n);
    for (int i = 0; i < 26; i++)
    {
        for (int j = 1; j < alphabet[i].size(); j++)
        {
            merge(alphabet[i][j - 1], alphabet[i][j]);
        }
    }
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i == parent[i])
            count++;
    }
    printf("%d", count);
    
    return (0);
}

 

위 그대로 짰다. 

 

아 이차원 벡터를 처음에 

vector<vector <int>> arr(6, vector<int> (5, 0));

 

이런식으로 했다가 

 

vector<int> alphabet(26) 이렇게 짜서 push_back 하려 했다가 컴파일 에러 떴다.

 

알고보니 (26)으로 하면 그냥 크기가 26인 벡터 하나가 만들어 지는 거고 [26]으로 해야지 벡터 베열이었다. 별거 아닌데 좀 놀랬음. 오! 그렇지 int arr[26], char arr[26] 처럼 벡터형인 배열이구나!

 

그러고보니 이거 전에 본 적 있는 것 같다. (머쓱..) 담에는 기억해서 써먹기로