[백준/Python,C] (S4) Least Common Divisor - 23516

Baekjoon Online Judge의 23516번 Least Common Divisor 문제의 Python, C언어 풀이입니다.

23516번: Least Common Divisor

💻코드

S, T = input(), input()

# s: 전체 문자열, p: 대상 문자열
def is_repeated(s, p):
    # 전체 문자열이 p의 반복으로 이루어져 있는지 확인
    return s == p * (len(s) // len(p))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

gcd_length = gcd(len(S), len(T))

# 최대공약수의 약수들을 순회하며 공통된 문자열 확인
for i in range(1, gcd_length + 1):
    if gcd_length % i == 0:
        P = S[:i]
        # 두 문자열이 해당 부분문자열의 반복으로 이루어져 있는지 확인
        if is_repeated(S, P) and is_repeated(T, P):
            # 조건을 만족하는 가장 짧은 공통 부분문자열을 찾으면 출력
            print(P)
            break
else:
    # 공통된 부분문자열이 없는 경우 "No solution"을 출력
    print("No solution")

#include <stdio.h>
#include <string.h>

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

// 주어진 패턴이 문자열에 반복되는지 확인하는 함수
int is_repeated(char *str, char *pattern, int pattern_len)
{
    int str_len = strlen(str);
    if (str_len % pattern_len != 0) // 문자열 길이가 패턴 길이로 나누어떨어지지 않으면 반복될 수 없음
        return 0;

    for (int i = 0; i < str_len; i++)
    {
        if (str[i] != pattern[i % pattern_len]) // 패턴과 일치하지 않는 문자가 있으면 0 반환
            return 0;
    }
    return 1; // 전체 문자열이 패턴으로 구성되어 있음
}

int main()
{
    char S[51], T[51];
    scanf("%s %s", S, T); // 문자열 입력

    int lenS = strlen(S), lenT = strlen(T);
    int gcd_len = gcd(lenS, lenT); // 두 문자열 길이의 최대공약수 계산

    for (int i = 1; i <= gcd_len; i++)
    {
        if (gcd_len % i == 0 && is_repeated(S, S, i) && is_repeated(T, S, i))
        {
            S[i] = '\0'; // 최소 공통 패턴 길이로 문자열 자름
            printf("%s", S); // 결과 출력
            return 0;
        }
    }

    printf("No solution"); // 공통 패턴이 없는 경우
    return 0;
}

🧠풀이

입력된 두 문자열 S와 T의 길이에 대한 최대공약수를 구한다.
이 최대공약수의 모든 약수에 대해, 가능한 모든 부분문자열을 확인한다.
해당 부분문자열이 두 문자열 모두에서 반복되는지 확인한다.
반복되는 가장 짧은 부분문자열을 찾으면 출력하고, 없으면 "No solution"을 출력한다.

🤔느낀 점

굳굳굳