Codeforces Round #747 (Div. 2)-C. Make Them Equal

문제 설명

지우에게 문자 $s_1,s_2,...,s_n$로 이루어진 문자열 $s$ 와 문자 $c$가 주어진다. 지우는 문자열에 있는 모든 문자를 최소 연산을 사용해서 $c$로 만들고 싶다.

우리가 사용해야할 연산은 다음과 같다.

• 지우는 $(1\le x\le n)$을 만족하는 숫자 $x$를 선택하고, $x$로 나누어 떨어지지 않는 모든 $i$에 대해서 $s_i$를 $c$로 바꾼다.

우리는 한 문자열에 있는 모든 문자를 $c$로 만들어야 하는 연산의 최소 개수를 구해야 한다.

Input
첫번째 줄에는 테스트 케이스의 수 $t(1\le t\le {10}^4)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 정수 $n$과 $(3\le n\le 3\cdot {10}^5)$ 소문자 알파벳 $c$가 주어진다.

각 테스트 케이스의 두번째 줄에는 모든 문자가 알파벳 소문자로만 이루어져 있는 문자열 $s$가 주어진다.

Output
각 테스트케이스마다 먼저 모든 문자를 $c$로 만들기 위해서 필요한 최소 연산의 개수 $m$을 출력한다.

그리고 다음 줄에 우리가 선택해야 하는 $m$개의 정수 $x_1,x_2,...,x_m(1\le x_j\le n)$ 을 출력한다.

만약 답이 여러개 있으면 아무거나 출력한다.

Example
input
3
4 a
aaaa
4 a
baaa
4 b
bzyx

output
0
1
2
2
2 3

문제 접근

사용한 알고리즘: 수학, 그리디 알고리즘, 완전탐색, 문자열
걸린 시간 : 00:11
진짜 조금만 더 하면 풀 수 있었는데 C번 문제의 벽에 막혔다. 진짜 아쉬웠던 문제. 이 문제의 핵심 부분은 잡아냈는데, 구현이 안된다 구현이.

이 문제에 핵심 포인트는 이 문제에 나올 수 있는 답은 3가지 뿐이라는 사실이다.

1. 문자열을 이루고 있는 모든 문자가 $c$로 이루어져 있다면 연산할 필요가 없기 때문에 답은 0이다.
2. 특정한 index를 선택하고 이 수와 그 수의 배수로 이루어져 있는 수에 대응되는 문자가 모두 $c$라면 이 index만 선택하면 나머지 문자가 $c$로 변하기 때문에 답은 1이다.
3. 위의 모든 경우가 아니라면 그냥 맨 뒤 문자와 맨 뒤에서 한칸 앞에 있는 문자를 선택하면 무조건 모든 문자를 다 바꿀 수 있기 때문에 답은 2이다.

여기서 우리가 구해야 하는 것은 2번 경우이다. 왜냐하면 1번 경우는 너무나 자명하고, 3번 경우는 보편적인 답이지만 최소 값이 아니기 때문이다.

이제 2번 경우를 어떻게 구해야하는지 생각해보자. 그런데 이것도 간단하다.

먼저 이것을 알아야 한다. 총 수가 $n$일때 $k$의 배수의 개수를 구하는 식은 $[n/k]$ 이고, $n$개의 배수를 모두 구하려면 시간복잡도는 $O(nlog(n))$ 이다. 자세한 내용을 알고 싶으면 구글에 조화수열 꼴 시간복잡도 구하기를 검색해보자. 나보다 자세하게 설명해 줄것이다.

따라서 문제에서 주어지는 $300000$ 인 경우는 시간 제한인 2초안에 충분히 구할 수 있다. 그렇기 때문에 완전탐색을 사용했다.

1번 index부터 그 index의 모든 배수를 구한다. 그 배수에 대응되는 문자 값이 $c$이면 넘어가고 $c$가 아닌경우는 답이 아니기 때문에 break 한다. 만약 모든 배수가 $c$이면 그 index가 답이고, 모든 배수가 위의 조건을 만족하지 않으면 답은 맨 뒤와 맨뒤에서 한칸 앞에 있는 수가 답이다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n;
        char c, s[3000010];
        cin >> n >> c >> s + 1;
        int idx = -1;
        for(int i = 1; i <= n; i++){
            idx = i;
            for(int j = i; j <= n; j += i){
                if(s[j] != c){
                    idx = 0;
                    break;
                }
            }
            if(idx) break;
        }
        if(idx == 1) cout << 0;
        else if(idx > 1) cout << 1 << "\n" << idx;
        else cout << 2 << "\n" << n << " " << n - 1;
        cout << "\n";

    }
    return 0;
}