글 읽기 - 1062-[시간복잡도 관련 질문] 2600만 연산이 1초 내에 안끝나나요??

qhrb1997 2년 전 0

우선 제 코드입니다. 다른 거 참고 안하고 그냥 저 혼자 개판으로 한 번 짜봤는데 시간초과가 나네요.

일단 next_permutation 이용해서 알파벳 조합들을 다 검사해주는 거로 했는데요. 우선 필요하지 않은 알파벳까지 조합을 계산해서 검사하다보니 시간이 오래 걸리는 것 같은데, 이유를 모르겠습니다.

최악의 경우로 21C10 * 50 * 15 해줘도 2600만 정도 되는데 이게 1초 내에 안끝나나요?? 제 코드에서 다른 부분에서 시간이 잡아 먹히는 건가요?? 시간복잡도도 N^2인거 같은데...

잘못된 부분 짚어주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, K;
vector<string> strlist;
vector<char> alphabet;

int getNum(int i) {
    if (i == 0) return i + 1;
    else if (i >= 1 && i < 6) return i + 2;
    else if (i >= 6 && i < 10) return i + 3;
    else if (i >= 10 && i < 15) return i + 4;
    else return i + 5;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;

    string tmp;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        sort(tmp.begin(), tmp.end());

        strlist.push_back(tmp);
    }

    for (int i = 0; i < 26; i++) {
        alphabet.push_back('a' + i);
    }

    vector<bool> alphas;
    for (int i = 0; i < 21; i++) {
        if (i < 26 - K) alphas.push_back(false);
        else alphas.push_back(true);
    }


    if (K < 5) {
        cout << 0;
        return 0;
    }

    sort(alphas.begin(), alphas.end());
    int maxCnt = 0;
    do {
        vector<char> comb;
        for (int i = 0; i < 21; i++) {
            if (alphas[i]) comb.push_back(alphabet[getNum(i)]);
        }
        comb.push_back('a');
        comb.push_back('c');
        comb.push_back('i');
        comb.push_back('t');
        comb.push_back('n');

        sort(comb.begin(), comb.end());

        int tmpCnt = 0;
        for (int i = 0; i < N; i++) {
            bool readImpossible = false;
            for (int j = 0; j < strlist[i].length(); j++) {
                if (!binary_search(comb.begin(), comb.end(), strlist[i][j]))
                    readImpossible = true;
            }
            if (!readImpossible)
                tmpCnt++;
        }

        maxCnt = max(maxCnt, tmpCnt);

    } while (next_permutation(alphas.begin(), alphas.end()));

    cout << maxCnt;


    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1062-[시간복잡도 관련 질문] 2600만 연산이 1초 내에 안끝나나요??

qhrb1997 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말