백준 12871 무한 문자열 c++

백준

문제 바로가기

문제

문자열 s가 있을 때, f(s)는 s를 무한번 붙인 문자열로 정의한다. 예를 들어, s = "abc" 인 경우에 f(s) = "abcabcabcabc..."가 된다.

다른 문자열 s와 t가 있을 때, f(s)와 f(t)가 같은 문자열인 경우가 있다. 예를 들어서, s = "abc", t = "abcabc"인 경우에 f(s)와 f(t)는 같은 문자열을 만든다.

s와 t가 주어졌을 때, f(s)와 f(t)가 같은 문자열을 만드는지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 f(s)와 f(t)가 같으면 1을, 다르면 0을 출력한다.

접근

입력받은 두 문자열의 길이를 비교해 길이가 더 긴 문자열이 짧은 문자열을 반복해서 포함하고 있는지 비교하고 다를 경우 0을 출력하게 했다.

처음 코드

#include <bits/stdc++.h>
using namespace std;


int min(int x, int y) {
    return x > y ? y : x;
}

int max(int x, int y) {
    return x > y ? x : y;
}

int main(int argc, char ** argv) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string s,p;
    cin >> s>>p;
    bool flag = true;
    if (s.size()>p.size()) {        
        int len = p.size();
        for (int i = 0;i < s.size();i++) {
            if (p[i%len] != s[i]) {
                flag = false;
                break;
            }
        }
    }
    else {        
        int len = s.size();
        for (int i = 0;i < p.size();i++) {
            if (s[i%len] != p[i]) {
                flag = false;
                break;
            }
        }
    }

    if (flag) cout << 1;
    else cout << 0;
}

틀렸습니다.

제출 후 1퍼 정도에서 바로 틀렸습니다를 받았다. 경험상(?) 채점 시작 후 곧바로 틀렸습니다 일 경우 입력의 양 끝에서 문제가 있는 경우가 많았다.

입력의 길이가 1일 경우 별다른 예외를 찾지 못해 길이가 50일 경우를 생각했다.

abcdef
abcdefabcdefabcdefabcdefabcdefabcdefabcdefabcdefab
코드 출력값 : 1
정답 : 0

처음 제출한 코드에서는 다음과 같이 주어진 문자열의 반복이 시작되는 시점에서의 값을 살피지 못하기 때문에 마지막 b값까지 같음을 확인하고 1을 출력한다.
이를 확인하기 위해 긴 문자열을 한번 이어붙여 반복 이후 여전히 짧은 문자열을 포함할 수 있는지 확인해 해결했다.

정답 코드

#include <bits/stdc++.h>
using namespace std;


int min(int x, int y) {
    return x > y ? y : x;
}

int max(int x, int y) {
    return x > y ? x : y;
}

int main(int argc, char ** argv) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string s,p;
    cin >> s>>p;
    bool flag = true;
    if (s.size()>p.size()) {
    	s+=s;
        int len = p.size();
        for (int i = 0;i < s.size();i++) {
            if (p[i%len] != s[i]) {
                flag = false;
                break;
            }
        }
    }
    else {
    	p+=p;
        int len = s.size();
        for (int i = 0;i < p.size();i++) {
            if (s[i%len] != p[i]) {
                flag = false;
                break;
            }
        }
    }

    if (flag) cout << 1;
    else cout << 0;
}