[CODEGROUND] 랩뮤직

#include <iostream> #include <fstream> #include <vector> #include <string> #include <algorithm> #include <functional> using namespace std; int result, rap_count; string rap; vector<int> alpha; void singing(int index, int rap_result) { if (index == rap_count) { result = max(result, rap_result); return; } int count = 0; while (index + count < rap_count) { count++; string temp = rap.substr(index, count); int sub_index = index + count - 1; while (1) { sub_index = alpha[sub_index]; if (sub_index == -1) break; if (temp.compare(rap.substr(sub_index, count)) == 0) singing(sub_index + 1, rap_result + 1); } } } int main() { int for_count; cin >> for_count; for(int i=1;i<=for_count;i++) { result = 0; cin >> rap_count; alpha = vector<int>(rap_count, -1); cin >> rap; for (int j = 0; j < rap_count; j++) { int before_index = j, alpha_index = rap[j] - 'a'; for (int k = j + 1; k < rap_count; k++) { if (rap[k] - 'a' == alpha_index) { alpha[before_index] = k; before_index = k; } } } singing(0, 0); cout << "Case #" << i << endl; cout << result << endl; } }

처음에는 시간을 줄이기 위해 다음 같은 알파벳을 저장해두었다.

a a b a b 라면

0 1 2 3 4

alpha라는 곳에 일단 a부터

1 3 -1 -1 -1 이렇게

이후 b를

1 3 4 -1 -1 이렇게 저장해 두었다.

이후 2중배열을 이용하여 바로바로 다음번 숫자를 이용할 수 있게 만들었다.

하지만..시간초과가 떴다

아마 2중배열을 이용한 데다 DP를 사용하였으니 시간이 오래걸릴 수 밖에 없다.

공유된 답은 정말..박수..

아직 초보라 코드를 고치고 해석하는데 오랜시간이 걸렸지만

앞으로 시간을 줄여나갈 수 있겠지!! 더 노력하자!!

#include <iostream> #include <vector> #include <queue> #include <fstream> #include <string> using namespace std; int rap_count; string rap; vector<vector<int> >adj; void pre(string pattern, int start_index) { int size_count = pattern.size(); vector<int>pattern_index = vector<int>(size_count); pattern_index[0] = 0; int patt_pre_index = 0; for (int pre_index = 1; pre_index < size_count; pre_index++) { while (patt_pre_index > 0 && pattern[pre_index] != pattern[patt_pre_index]) patt_pre_index = pattern_index[patt_pre_index - 1]; if (pattern[patt_pre_index] == pattern[pre_index]) { patt_pre_index++; pattern_index[pre_index] = patt_pre_index; } else pattern_index[pre_index] = 0; if (pattern_index[pre_index] != 0) adj[start_index].push_back(start_index + pre_index + 1); } } int singing() { vector<int> visit = vector<int>(rap_count + 1, -1); queue<pair<int, int> >cache; cache.push(make_pair(0, 0)); visit[0] = 1; while (!cache.empty()) { int here = cache.front().first; int count = cache.front().second; cache.pop(); for (int j = 0; j < adj[here].size(); j++) { if (visit[adj[here][j]] == -1) { int there = adj[here][j]; visit[there] = 1; if (there == rap_count) return count + 1; cache.push(make_pair(there, count + 1)); } } } return 0; } int main() { int for_count; cin >> for_count; for (int i = 1; i <= for_count; i++) { cin >> rap_count >> rap; adj = vector<vector<int> >(rap_count + 1); for (int index = rap_count - 1; index >= 0; index--) pre(rap.substr(index, rap_count), index); cout << "Case #" << i << endl; cout << singing() << endl; } }

코드의 전체적인 알고리즘은

먼저 뒤에서부터 반복되는 구간을 미리 구해놓는다

그리고 bfs로 푼다.

간단하게 말하면 이정도이다.

그럼 자세하게 설명을 해본다.

일단 pre라는 함수를 보자

이함수는 main의 for문에서부터 왔다.

길이가 2인 pattern string부터 시작한다. aa도 패턴이니까

그럼 우리는 어떻게 저장을 하냐면

adj라는 이중배열을 만든다

그리고 시작하는 index가 첫번째 index이고 그 이후에

반복되는 문자 다음 index를 넣는다

그게 무슨소리냐 하면

aababa라면 여기서 baba를 잘라서 확인해본다고 가정하자

ba와 ba는 패턴을 가진다 그렇다면 baba의 시작점이 전체 string배열에서 2번째 index에 있으므로

adj[2]배열에 집어넣는다 여기서 ba의 패턴의 다음 index를 집어넣는것이다. 그렇다면

adj[2] = 원래 시작하는 index가 2 (전체 rap string에서의 index) 이고 ba의 패턴이 끝나는 때가 (a의 index(3)(pre함수에서 잘라진 pattern string에서의 index)+1)이다

즉 adj[2]에 6을 집어넣어주는 것이다

이렇게 뒤에서부터 계속 반복한다

그럼 다음줄을 넘어가보자

pattern_index는 왜 만들어졌을까?

이 pattern_index에는 만약 값이 같다면 현재 값에 다음값으로 넘어가라는 의미로 다음 index를 넣어놓았다.

그리고 시작해보자

일단 pre_index=1일때이다

그리고 그 밑에 while문이 보일 것이다.

이 while문은 이런뜻이다 만약

CAB라는 패턴을 이미 파악해놓았고, pattern_index에 C : 0 A : 1 B : 2라는 값을 저장해놓았다고 하자

만약 새로운 값이 발견되었을 때 그 값이 A라면

while문을 돌려서 B부터 차례대로 다시 제자리 값으로 돌아가는 것이다

한 가지 예를 더 들어보자 만약 CABDCAECA라는 문자가 있다고 가정하자

그렇다면 우리는 C가 ptt_pre_index=0이므로 계속 비교를 하다가 두 번째 나오는 C에서 한칸 움직일 것이다

그리고 C : 0 A : 0 B : 0 D : 0 C : 1 (pattern_index에는 다음에 비교할 대상이 있는 index값을 넣어준다) 이되고 ptt_pre_index가 1이 증가한다

그럼 우리는 A가 ptt_pre_index=1이므로 현재 두번째 A와 비교한다 역시 맞다 따라서

C : 0 A : 0 B : 0 D : 0 C : 1 A : 2로 변경해준다

이후 E라는 숫자가 나왔다 결국 맞지 않으므로 E : 0 하지만 뒤에 보면 C라는 값이 나왔다

다시 패턴의 시작이다. 따라서 C로 비교해야한다. 하지만 patt_pre_index는 아무런 조치도 취하지 않았다.

즉 현재 patt_pre_index가 가르키는 값은 B이다.

따라서 while을 쓰는 것이다.

patt_pre_index는 현재 2이다 즉 pattern_index[patt_pre_index-1]을 하면 0이나온다

0은 일단 첫번째 patt_pre_index>0에도 위배되지만 pattern[patt_pre_index]!=pattern[pre_index]에도 위배되므로 빠져나가고

다시 C부터 패턴감지를 시작할 수 있다

결국 여기서는 CA CA가 패턴이므로 C : 0 A : 0 B : 0 D : 0 C : 1 A : 2 E : 0 C : 1 A : 2 가 될 것이다.

(pre는 나눠진 string pattern이라는 게 들어오고 그 pattern 의 첫번째 부터 마지막까지의 패턴을 찾는 것이 목표이다.

 따라서 pattern_index 배열에 중간에 C A가 있더라도  5 6이 들어가지 않고 1 2 가 들어간다.

 그리고 pattern_index는 너가 다음에 비교할 패턴 문자는 이거야 라고 알려주는 배열이다.

 따라서 다음에 들어갈 문자가 있는 index를 저장해준다.)

그렇다면 그다음 index는 A이고 A는 패턴에 맞다.

patt_pre_index가 0 초과여야하는 이유는 배열에 음수가 들어가지 않게 하기 위함이다

그렇다면 계속 if문이 시작되고 이어서 else문이다

만약 패턴이 있다면 그 다음 문자도 패턴인지 확인하기 위해 patt_pre_index를 1개 늘여준다

만약 패턴이 없다면 결국 처음부터 패턴을 찾아야한다는 뜻이다.

따라서 pattern_index를 처음으로 돌린다.

그리고 만약 pattern_index가 0이 아니라면 시작부분과 맞는 문자열이 있다는 것을 확인하는 것이기 때문에

위의 adj규칙으로 넣어준다.

즉 pre는 뒤에서부터 한개씩 문자를 늘여가면서 패턴이 있는지 먼저 확인해 놓는 곳이다.

이후 bfs를 한다.

이 bfs는 얼마나 깊이 들어갔는지가 결국 답이 된다.

따라서 pair<int,int>로 queue를 구성했다.

처음이 index 뒤가 count로 해서 현재 count를 가져오도록 했다.

그리고 만약 새로 들어온 즉 내가 뻗은 곳의 index가 rap.size()와 같다면 이것은 마지막에 도달했다는 뜻이므로 값을 return해준다.