백준 1062번 가르침 (C++)

문제설명

 

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

1062번: 가르침

 

문제해결

 

전체적인 코드 흐름은 다음과 같다. 

1. default_alpha에 항상 들어가는 5개의 알파벳을 넣어준다. 
2. 최적화를 하기 위해 백트래킹에서는 default_alpha에 해당하는 문자들은 탐색하지 않았다. 따라서 문장들을 탐색하면서 default_alpha에 해당하는지 검사한다. 만약 default_alpha에 속하면 이미 검사를 완료했다는 의미로 word_dup을 1로 바꿔주고, (추후 배웠는지 탐색할 때 이 알파벳도 보아야 하므로) 속하지 않으면 alpha에 넣어준다. 
3. sort, unique, erase 함수를 사용하여 alpha에 있는 중복값들을 제거해준다. 
4. for문을 돌며 백트래킹으로 탐색한다. 여기서부터는 조합 문제와 유사하다. 
5. 백트래킹에서는 현재 뽑은 개수와 인덱스가 인자로 들어간다. for문을 돌면서 재귀로 호출한다. 
6. 종료 조건은 뽑은 개수가 입력으로 주어진 k값과 같아지거나, alpha의 사이즈보다 커질때이다. 여기서 alpha는 중복되지 않은, 배워야 하는 추가적인 알파벳들이 담겨있는 리스트이다. 
7. 종료될 때 cnt_sent 함수를 호출하여 이미 배운 문장인지 아닌지 탐색하고, 배운 문장일 경우 값을 늘려준다. 
8. 기존 max값과 비교하여 더 크면 갱신시켜준다.  

 

트러블슈팅

1. 다 배웠는지 확인하는 부분의 코드를 비효율적으로 짰어서 조금 헤맸던 문제이다. 처음에는 백트래캥으로 탐색하는 과정에서 set 자료구조인 default_alpha에 값을 추가하는 식으로 했는데, 이렇게 하니 각 알파벳 별로 확인하기 위해 find()함수를 써야 했고, 한 글자당 O(logn)의 시간이 걸리므로 제한 시간인 1초를 넘어갔다. 따라서 중복 여부를 확인하는 int 배열 (각 인덱스는 알파벳을 의미)를 선언하여 바로 확인이 가능하도록 하였다. 
2. 위 이유로 default_alpha를 set으로 설정했는데, 현재 코드에서 굳이 이럴 이유는 없어보인다. 
3. 처음에는 중복된 알파벳을 탐색하는 것을 방지하기 위해 alpha를 set 자료구조로 했는데, set 자료구조는 인덱스 접근이 불가능하여, list 자료구조로 바꾸었다. 중복을 제거하기 위해 unique 함수를 사용하였다. unique 함수는 앞에서부터 탐색하여 중복된 값들과 중복되지 않은 값을 바꿔주는 역할을 한다. 이러한 함수의 특성 때문에 두가지 주의점이 있다. 함수의 원리를 제대로 찾아보지 않고 사용하였더니 중복된 값이 남아버리는 문제가 있었다. 
   1. 앞에서부터 차례로 비교하기 때문에 정렬되어 있지 않은 상태에서는 제대로 동작하지 않는다. 
   2. 배열의 길이를 바꿔주지 않는다. 따라서, 중복된 값들이 뒤에 남아있다. 중복되지 않은 값들을 얻고 싶다면, erase 함수를 사용하여 unique 다음 부터 해당 배열 끝까지를 지워줘야 한다.
4. 백트래킹을 돌기 위해 for문을 호출할 때, 처음에는 alpha size에서 k를 제거했었다. 그 이유는 k개를 뽑기 때문에 size - k 인덱스 이후부터는 검색할 필요가 없다고 느꼈기 때문이다. 하지만 k <= alpha size라는 보장이 없기 때문에 음수로 갈 수 있는 가능성이 존재에서 제거하였다. (문장 수가 적은데도 시간이 오래걸렸던 이유) 
5. 백트래킹 함수 내에서 재귀로 호출하고, 다시 word_dup 배열값을 0으로 바꾸지 않으면 이후 배운 문장을 탐색하는 데에 문제가 발생한다. 

코드

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector <char> alpha;
set <char> default_alpha {'a', 'c', 'i', 'n', 't'};
string word[51];
int word_dup[27] = {0, }; //중복방지 
int n, k;
int max_word = 0;

int cnt_sent(string s)
{
    int cnt = 0;
    for (int i = 0; i < s.size(); i++)
    {
       if (!word_dup[s[i] - 'a']) 
            cnt++;
    }
    return (cnt);
}

void dfs(int cnt, int idx)
{
    if (cnt == k || cnt >= alpha.size()) //다 뽑았으면 
    {
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            int tmp = cnt_sent(word[i]);
            if (tmp == 0) //모두 배운 경우
                res++;
        }
        if (res > max_word)
            max_word = res;
        return ;
    }
    if (idx >= alpha.size())
        return ;
   for (int i = idx; i < alpha.size(); i++)
    {
        if (!word_dup[alpha[i] - 'a'])
        {
            word_dup[alpha[i] - 'a'] = 1;
            dfs(cnt + 1, i + 1);
            word_dup[alpha[i] - 'a'] = 0;
        }

    }
}

int main(void)
{
    int res = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> word[i];
        for (int j = 0; j < word[i].size(); j++)
        {
            if (default_alpha.find(word[i][j]) == default_alpha.end())
                //default가 아니면 
                alpha.push_back(word[i][j]);
            else //default는
                word_dup[word[i][j] - 'a'] = 1;
        }
    }
    if (k < 5)
    {
        cout << "0" << "\n";
        return (0);
    }
    sort(alpha.begin(), alpha.end());
    alpha.erase(unique(alpha.begin(), alpha.end()), alpha.end()); 
    //중복 제거를 unique만 쓰면 되는 줄 알았는데 erase로 지워주기까지 해야함
    //쓰기 전에 sort로 정렬해줘야함 
    k -= 5; //기본값 5개
    for (int i = 0; i <= alpha.size(); i++)
        dfs(0, i);
    cout << max_word << "\n";
}

 

 

참조

unique 함수 동작원리 

https://velog.io/@whipbaek/c-unique-%ED%95%A8%EC%88%98%EC%97%90-%EA%B4%80%ED%95%98%EC%97%AC

c++ unique() 함수에 관하여