[백준/파이썬][Silver V] 무한 문자열 - 12871

[Silver V] 무한 문자열 - 12871

문제 링크

성능 요약

메모리: 108384 KB, 시간: 92 ms

분류

구현, 수학, 문자열

제출 일자

2025년 2월 6일 22:20:49

문제 설명

문자열 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을 출력한다.

풀이

def gcd(a, b) :
    while b:
        a, b = b, a%b
    return a
def lcm(a, b) :
    return abs(a * b) // gcd(a, b)

def main() :
    s = input()
    t = input()

    ls = len(s)
    lt = len(t)

    nums = lcm(ls, lt)
    if nums == -1 :
        return 0

    else :
        cnt_s = nums // ls
        cnt_t = nums // lt

        fs = s * cnt_s
        ft = t * cnt_t

        if fs == ft :
            return 1
        else :
            return 0

print(main())

 

def main() :
    a = input()
    b = input()
    print(int(a+b == b+a))


T = int(input())
for _ in range(T) :
    main()

첫 풀이에는 최소 공배수로 뭐 어떻게 해야겠다고 생각해서 저렇게 풀었는데

다른 분의 풀이를 보니, 이렇게 간단하게 생각할 수도 있구나고 느꼈다.

어떤 반복이 일어나던 반복이 일어나게 되면 두 문자를 합치게 되면 같아야 한다는 걸 빨리 깨달았다면 쉽게 문제를 풀 수 있을 것이다. 새로운 문제 풀이 방식이 참 반갑다.