구현(무한 문자열/S5) - 12871

1. 문제

문자열 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)가 같은 문자열을 만드는지 아닌지 구하는 프로그램을 작성하시오.

 

2. 입력

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

ab
abab

 

abc
bca

 

3. 출력

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

1

 

0

 

4. 코드

- 틀린풀이 : 입력값을 abab, ababab로 넣으면 0이 나옴

import sys

input = sys.stdin.readline
s = input().rstrip()
t = input().rstrip()

def check(m, n):
  for i in range(0,len(m),len(n)):
    if m[i:i+len(n)] != n:
      return 0
  return 1
  
if len(t) > len(s):
  print(check(t, s))
else:
  print(check(s, t))

 

 

- 맞는 풀이

import sys

input = sys.stdin.readline
s = input().rstrip()
t = input().rstrip()

def multiple(a, b):
  j= max(a,b)
  for i in range(j, (a*b)+1):
    if i%a == 0 and i%b == 0:
      return i;
      
m = multiple(len(s),len(t))

s = s*(m//len(s))
t = t*(m//len(t))

if(s==t):
  print(1)
else:
  print(0)

 

5. 풀이설명

① 입력값 s와 t를 입력받는다.

② multiple 메소드로 s와 t의 최소공배수를 구한다.

 

③ s와 t의 길이가 최소공배수 m이 되도록 수정하여 s와 t에 대입한다.

 

④ s와 t가 같으면 1 다르면 0을 결과값으로 출력한다.

 

 

6. 느낀점

처음에는 s와 t중 길이가 짧은 문자를 반복시켜 길이가 긴 문자와 같은지를 확인하여 구했으나 예외 상황이 존재했다.

구글링 후 s와 t를 s와 t의 최소공배수 길이가 될 때까지 반복하여 두 문자가 같은지 확인하였다.