[C++] Kick Start 2018 Round A - Scrambled Words(large dataset 시간초과)

0. [C++] Kick Start

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edf/0000000000051004

1. 풀이

단어의 앞, 뒤가 일치하면 문자열을 새롭게 만들어 정렬 후 비교를 통해 일치하는지 확인하였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

#include<iostream> #include<string> #include<algorithm> #include<vector>   using namespace std;   string arr[20001];   string S_Generator(char x_1, char x_2, int N, int A, int B, int C, int D) {     string S;     S += x_1;     S += x_2;     long long int x[3];     x[0] = x_1; x[1] = x_2; x[2] = 0;     while (1) {         if (S.length() == N) {             return S;         }         x[2] = (A*x[0] + B * x[1] + C) % D;         S += char(97 + x[2] % 26);         x[0] = x[1];          x[1] = x[2];         x[2] = 0;     }      }   int checkWord(const int& N, const string& S) {     int count = 0;     for (int k = 0; k < N; k++) {         int word_Length = arr[k].length();           string midText = arr[k].substr(1, word_Length - 2);         sort(midText.begin(), midText.end());           for (int i = 0; i < S.length() - word_Length + 1; i++) {             //앞뒤가 일치하면 탐색 시작.             if (S[i] == arr[k][0] && S[i + word_Length - 1] == arr[k].back()) {                 string midText_ = "";                 for (int j = 1; j < word_Length - 1; j++) {                     midText_ += S[i + j];                 }                 sort(midText_.begin(), midText_.end());                 if (midText == midText_) {                     count++;                     break;                 }             }         }     }          return count; }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     int T, L, N, A, B, C, D;     char S_1, S_2;          cin >> T;     for (int i = 1; i <= T; i++) {         cin >> L;         for (int j = 0; j < L; j++) {             cin >> arr[j];         }           cin >> S_1 >> S_2 >> N >> A >> B >> C >> D;         vector<int> X(N);         X[0] = S_1;         X[1] = S_2;         for (int i = 2; i < N; ++i) X[i] = ((long long)A*X[i - 1] + (long long)B*X[i - 2] + C) % D;         string S;         S.resize(N);         S[0] = S_1;         S[1] = S_2;         for (int i = 2; i < N; ++i) S[i] = char('a' + X[i] % 26);           //string S = S_Generator(S_1, S_2, N, A, B, C, D);           cout << "Case #" << i << ": " << checkWord(L, S) << "\n";     } }   Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!