텍스트 분석에서 빅그램(Bigram)은 연속된 두 단어의 쌍을 의미합니다. 이번 문제에서는 텍스트 안에서 "첫 번째 단어(first) → 두 번째 단어(second) → 세 번째 단어(third)" 형태로 나타나는 패턴을 찾아야 합니다. 즉, second가 first 바로 뒤에 등장하고, third가 second 바로 뒤에 등장하는 모든 경우를 찾는 것입니다.
이러한 패턴을 발견할 때마다 해당 위치의 third 단어를 결과 리스트에 추가하고, 최종적으로 그 리스트를 반환하면 됩니다.
예를 들어 텍스트가 "lina is a good girl she is a good singer"이고, first = "a", second = "good"이라면, 텍스트 내에서 "a good"이라는 빅그램이 두 번 등장하고 각각 뒤에 "girl"과 "singer"가 따라오므로 정답은 [girl, singer]가 됩니다.
문제 해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 주어진 텍스트를 공백을 기준으로 분리하여 단어 리스트로 만듭니다.
- 결과를 저장할 빈 리스트(res)를 생성합니다.
- 리스트의 처음부터 끝까지 반복문을 돌면서 다음 조건을 확인합니다.
- 현재 인덱스 i에서 i+2가 텍스트 길이보다 작고(범위 초과 방지),
- text[i]가 first와 같으며,
- text[i+1]이 second와 같다면,
- text[i+2](즉, third 단어)를 결과 리스트에 추가합니다.
- 반복이 끝나면 결과 리스트를 반환합니다.
구현 예제
아래 코드를 통해 실제 구현 과정을 더 쉽게 이해할 수 있습니다.
class Solution(object):
def findOcurrences(self, text, first, second):
text = text.split(" ")
res = []
for i in range(len(text)):
if i + 2 < len(text) and text[i] == first and text[i+1] == second:
res.append(text[i+2])
return res
ob1 = Solution()
print(ob1.findOcurrences("lina is a good girl she is a good singer", "a", "good"))코드 설명
text.split(" "): 문자열을 공백 기준으로 나누어 단어 리스트로 변환합니다.i + 2 < len(text): 세 번째 단어가 실제로 존재하는지 확인하여 인덱스 오류를 방지합니다.res.append(text[i+2]): 조건을 만족하면 빅그램 바로 뒤의 단어를 결과에 저장합니다.
입력
"lina is a good girl she is a good singer" "a" "good"
출력
['girl', 'singer']
시간 복잡도
이 알고리즘은 텍스트의 단어 수를 n이라 할 때, 한 번의 순회로 모든 패턴을 찾으므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 결과 리스트 크기에 비례하여 O(n)입니다. 매우 효율적인 방식으로 빅그램 이후의 단어를 추출할 수 있습니다.