[C/C++] BOJ 1062 :: 가르침

BOJ 1062 :: 가르침

문제 링크 : https://www.acmicpc.net/problem/1062

ㅠㅠ 2시간 넘게 풀었는데 계속 시간초과가 나서 다른 분들이 푼 것을 참고하여 풀었다..

우선, 내가 시간을 줄이기 위해 고려해준 조건들은

1) 단어의 처음과 끝의 "anta" 와 "tica" 를 제외하고 단어를 저장한다.

2) K가 5보다 작을 경우, a, n, t, i, c 를 읽을 수 없으므로 0을 출력한다.

3) K가 5이상이고 K개의 글자를 가르쳤을 때, 단어 중 가르치지 않은 문자가 포함되어 있다면 바로 다음 단어를 탐색한다.

이와 같다.

그러나 내가 고려해주지 못한 조건들이 있었다.

1) "anta"와 "tica"를 제외할 때 나는 문자 하나하나를 탐색하며 제거해나가 시간이 매우 오래 걸렸다..

==> 이것을 앞 4글자, 뒤 4글자를 떼어내는 방식으로 바꾸어야 했다.

2) 가르칠 수 있는 단어 K가 26일 때, 모든 단어를 읽을 수 있으므로 N을 출력하면 된다.

3) 가르칠 수 있는 알파벳을 체크해나갈 때, 배열의 시작 index를 check한 다음의 index로 갱신해주어야 for문의 범위를 줄일 수 있는데 그 부분을 간과했다. 

세 번째 같은 경우는 정말 기본적인 건데 생각하지 못한 것이 너무 아쉬웠다 ㅠㅠ..

첫 번째 같은 경우, 문자를 하나하나 탐색해가며 앞의 "anta" 뒤의 "tica" 말고도 단어의 중간에 있는 a,n,t,i,c를 제거하려다 보니 이런 구현을 하게 되었는데 조금만 더 생각해서 이러한 구현보다는 앞과 뒤만 떼어내는 것이 더 효율적이라는 것을 빨리 깨달았으면 좋았을 걸 싶다 ㅠㅠ

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1062/BOJ_1062.cpp

// 백준 알고리즘 1062번 :: 가르침
#include<iostream>
#include<string>
using namespace std;
 
int N, K;
int ans = 0;
string sentence[51];
bool alpha[26];
 
int findmaxwordnum()
{
    int count = 0;
 
    for (int i = 0; i < N; i++)
    {
        bool flag = true;
        int stlen = sentence[i].size();
        for (int j = 0; j < stlen; j++)
        {
            if (!alpha[sentence[i][j] - 'a']) flag = false;
            if (!flag) break;
        }
        if (flag) count++;
    }
    return count;
}
void simulate(int start, int count)
{
    if (count == K - 5) {
        // 읽을 수 있는 문장 개수 구하기
        int numword = findmaxwordnum();
        // ans 갱신하기
        if (ans < numword) ans = numword;
        return;
    }
    // 알파벳 체크하기
    // 내가 고려하지 못한 것!!!!!!!!!!!!!!!!!!!!! (3)
    for (size_t i = start; i < 26; i++)
    {
        if (alpha[i]) continue;
        alpha[i] = true;
        simulate(i+1, count + 1);
        alpha[i] = false;
    }
    return;
}
 
int main()
{
    string str;
    cin >> N >> K;
 
    // 내가 고려하지 못한 것!!!!!!!!!!!!!!!!!!!!! (1)
    for (int i = 0; i < N; i++)
    {
        cin >> str;
        //anta
        str = str.substr(4, str.length());
 
        //tica
        for (int j = 0; j < 4; j++)
            str.pop_back();
 
        sentence[i] = str;
 
    }
 
    // K가 5이상일 때에만 simulate한다.
    // 그렇지 않은 경우는 "anta"+"tica"를 읽을 수 없으므로 0을 출력한다.
    // K가 26일 때에는 모든 단어를 읽을 수 있다.
 
    // 내가 고려하지 못한 것!!!!!!!!!!!!!!!!!!!!! (2)
    if (K == 26) ans = N;
    else if (K >= 5)
    {
        alpha['a' - 'a'] = true;
        alpha['n' - 'a'] = true;
        alpha['t' - 'a'] = true;
        alpha['i' - 'a'] = true;
        alpha['c' - 'a'] = true;
 
        simulate(0,0);
    }
 
    cout << ans;
 
    return 0;
}