문제 개요
두 문장 s와 t가 주어졌을 때, 이 두 문장이 유사한지 판별하는 프로그램을 만들어 보겠습니다. 여기서 문장은 영어 알파벳으로만 구성된다고 가정합니다.
두 문장이 유사하다는 것은, 한 문장의 임의의 위치에 다른 문장(빈 문장도 허용)을 삽입했을 때 두 문장이 완전히 같아질 수 있는 경우를 의미합니다.
예를 들어, 입력이 s = "we live at city Kolkata", t = "city Kolkata"라면 결과는 True입니다. t의 앞부분에 "we live at"이라는 단어들을 추가하면 s와 동일해지기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다:
- s1 := s를 단어 단위로 분리한 리스트
- s2 := t를 단어 단위로 분리한 리스트
- s1의 길이가 s2보다 크다면, s1과 s2를 서로 교환합니다.
- s1이 빌 때까지 다음을 반복합니다:
- s2의 첫 번째 단어가 s1의 첫 번째 단어와 같으면, 두 리스트에서 첫 번째 단어를 제거합니다.
- 그렇지 않고 s2의 마지막 단어가 s1의 마지막 단어와 같으면, 두 리스트에서 마지막 단어를 제거합니다.
- 둘 다 해당하지 않으면 false를 반환합니다.
- 반복이 정상적으로 끝나면 true를 반환합니다.
구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
def solve(s, t):
s1 = s.split()
s2 = t.split()
if len(s1) > len(s2):
s1, s2 = s2, s1
while(s1):
if(s2[0] == s1[0]):
s2.pop(0)
s1.pop(0)
elif(s2[-1] == s1[-1]):
s2.pop()
s1.pop()
else:
return(False)
return(True)
s = "we live at city Kolkata"
t = "city Kolkata"
print(solve(s, t))
입력
"we live at city Kolkata", "city Kolkata"
출력
True
알고리즘 동작 원리
이 알고리즘의 핵심 아이디어는 짧은 문장이 긴 문장의 앞부분, 뒷부분, 또는 중간에 삽입될 수 있다는 점에 착안합니다. 짧은 문장의 단어들을 긴 문장의 앞에서부터와 뒤에서부터 순서대로 비교하며 일치하는 단어를 제거해 나가면, 짧은 문장이 완전히 소모되는 순간 두 문장은 유사하다고 판단할 수 있습니다.
중간에 불일치가 발생하면 어떤 위치에 단어를 삽입해도 두 문장을 같게 만들 수 없으므로 즉시 false를 반환합니다. 이 방식의 시간 복잡도는 단어 수를 n이라 할 때 O(n)으로 효율적입니다.