출처 : https://www.acmicpc.net/problem/4354
문자열 제곱 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 764 | 346 | 255 | 49.611% |
문제
두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.
이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.
a^0 = "" (빈 문자열)
a^(n+1) = a*(a^n)
문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장큰 n을 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표를 포함하고 있다.
출력
각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.
예제 입력
abcd aaaa ababab .
예제 출력
1 4 3
힌트
출처
Contest > Waterloo's local Programming Contests > 1 June, 2002 D번
- 문제를 번역한 사람: baekjoon
>> 풀이 방법
a^n 꼴에서 a로 가능한 후보들을 먼저 구한다.
글자의 길이가 n이면 가능한 a 는 1보다 크거나 같고 n/2 와 작거나 같은 숫자 중에서
글자의 길이를 나눴을 때 나머지가 0인 숫자만 queue 에 밀어 넣는다.
가장 작은 숫자가 queue 에 먼저 들어가게 된다.
작은 글자 부터 탐색을 시작하여 조건을 만족하는지 확인한다.
작은 글자부터 하는 이유는 n 이 가장 큰 경우를 구하는 것이기 때문에, 가능한 경우가 바로 나오면 답으로 출력하기 위해서이다.
KMP 알고리즘에 대한 설명 : http://bowbowbow.tistory.com/6
문자열 알고리즘 설명 : https://namu.wiki/w/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
다른 빠른 풀이들은 KMP 알고리즘을 사용했다.
나 같은 경우에는 KMP 를 사용하지 않았지만, 이 문제 같은 경우에는 KMP 의 사용 여부와 상관없이 문제가 풀렸다.
KMP 의 시간 복잡도가 O(N+M) 이고 , 단순한 비교 방법이 O(NM)이다.
일부러 KMP를 이용하라고 문제를 만들었으면, 시간 복잡도가 O(NM)으로 풀었으면 무조건 틀렸을 것이다.
하지만 이 문제에서는 사용 가능한 a 의 크기들을 구하고 만약에 비교하다가 틀린 것이 발견 되면
도중에 바로 해당 크기의 비교를 중단해도 되기 때문에, KMP로 굳이 안풀어도 되는 문제이다.
아래의 문자열을 2의 크기로 비교를 했다고 가정해보자.
cdecdeckecde
먼저 처음 cd를 기준으로 4,5,6번째 글자를 비교하여 이상이 없기 때문에 다음 라운드로 넘어간다.
그 다음에 7,8,9을 조사하는데 k 가 있어서 8에서 끝나게 된다.
KMP 라면
내 풀이의 시간 복잡도는 후보(약수의 개수)를 a 라고 하고, 약수 하나당 패턴과 나머지 글자의 최대 비교 회수는 글자의 길이인 N이다(모든 수가 일치 or 마지막에서 틀림)
따라서, 최대 시간 복잡도는 O(aN)이다.
약수의 개수는 통상적으로 매우 적은 숫자이기 때문에(N0.5 보다 작다), 총 시간 복잡도는 O(N1.5) 보다는 무조건 작을 것이다.
O(N1.5) 일때 1,000,000 크기의 글자가 들어오면, 10억이 되어 너무 크고
O(N1.3) 일때 1,000,000 크기의 글자가 들어오면, 6천만 정도의 크기를 가진다.
정확한 크기는 잘 모르겠지만, a(약수의 개수)가 N1.3보다 작거나 비슷할 것으로 판단된다.
- 정확한 크기를 구할 수 있는 분은, 댓글이나 메일 주세요 ㅜ
>> 소스 코드
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 | #include <iostream> #include <queue> #define MAX_SIZE 1000000 #pragma warning(disable: 4996) using namespace std; char char_arr[MAX_SIZE]; int main() { while (true) { scanf("%s", char_arr); int char_length = 0 ; // 종료 구간에서 while문 종료 if (char_arr[0] == '.') break; // 글자 길이 결정 while (char_arr[char_length]) char_length++; queue<int> hoobo; // 후보 구하기 for (int i = 1; i <= char_length/2; i++) { if ((char_length % i) == 0) hoobo.push(i); } hoobo.push(char_length); // 후보의 갯수만큼 확인해본다. 정답이 나오면 바로 답을 출력한다. while (hoobo.size()) { int nowHooBo = hoobo.front(); hoobo.pop(); int isHooBo = 1; for (int rep_num = 0; rep_num < (char_length/nowHooBo -1); rep_num++) { for (int i = 0; i < nowHooBo; i++) { if (!isHooBo) break; if (char_arr[i] != char_arr[i + (rep_num + 1) *nowHooBo]) isHooBo = 0; } } // 전부 일치하면 if (isHooBo) { printf("%d\n", char_length / nowHooBo); break; } } } return 0; } | cs |