두 개의 문자열 s0과 s1이 있고, 각각 하나의 문장을 나타낸다고 가정해 봅시다. 이때 두 문장에 공통으로 등장하는 고유한 단어의 개수를 구하는 것이 목표입니다.
주의할 점은 단어를 비교할 때 대소문자를 구분하지 않는다는 것입니다. 예를 들어 "tom"과 "ToM"은 같은 단어로 취급됩니다.
문제 예시
입력이 다음과 같다고 해보겠습니다.
- s0 = "i love python coding"
- s1 = "coding in python is easy"
이 경우 두 문장에 공통으로 포함된 단어는 ['python', 'coding'] 두 개이므로, 출력 결과는 2가 됩니다.
해결 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 문자열 s0과 s1을 모두 소문자로 변환합니다.
- s0List := s0을 공백 기준으로 나눈 단어 리스트
- s1List := s1을 공백 기준으로 나눈 단어 리스트
- s0List와 s1List 각각을 집합(set)으로 변환한 뒤 교집합을 구하고, 그 결과의 개수를 반환합니다.
집합(set) 자료형을 활용하면 중복 제거와 교집합 연산이 매우 간단해집니다. 아래 구현 예시를 통해 더 자세히 살펴보겠습니다.
구현 예제
class Solution:
def solve(self, s0, s1):
s0 = s0.lower()
s1 = s1.lower()
s0List = s0.split(" ")
s1List = s1.split(" ")
return len(list(set(s0List)&set(s1List)))
ob = Solution()
S = "i love python coding"
T = "coding in python is easy"
print(ob.solve(S,T))
입력
"i love python coding", "coding in python is easy"
출력
2
코드 설명
위 코드의 동작 과정을 단계별로 정리하면 다음과 같습니다.
- lower(): 문자열 전체를 소문자로 변환하여 대소문자 차이로 인한 비교 오류를 방지합니다.
- split(" "): 공백을 기준으로 문장을 단어 단위 리스트로 분리합니다.
- set() & set(): 각 리스트를 집합으로 만든 후 & 연산자(교집합)로 공통 단어만 추출합니다.
- len(): 교집합에 포함된 단어의 개수를 최종 결과로 반환합니다.
이 방식의 시간 복잡도는 대략 O(n + m)입니다(n, m은 각 문장의 길이). 집합 변환과 교집합 연산이 선형 시간에 수행되기 때문에 문장이 길어져도 효율적으로 동작합니다.