문제 소개
두 개의 리스트가 주어졌다고 가정해 보겠습니다. 하나는 몇 가지 선별된 구문(phrase)을 담고 있는 phrases 리스트이고, 다른 하나는 해당 구문들이 포함되어 있을 수도 있고 없을 수도 있는 여러 문장을 담고 있는 sentences 리스트입니다. 우리가 해야 할 일은 첫 번째 리스트의 각 구문이 두 번째 리스트의 문장들 속에서 실제로 사용되는지 확인한 뒤, 등장 횟수를 기준으로 구문을 정렬하여 그 결과를 반환하는 것입니다.
예를 들어 입력이 다음과 같다면,
phrases = ['strong', 'durable', 'efficient']
sentences = ['the product is durable and efficient',
'strong and durable',
'it is efficient',
'like it because it is efficient']
출력은 다음과 같아야 합니다.
['efficient', 'durable', 'strong']
'efficient'는 세 개의 문장(인덱스 0, 2, 3)에 등장해 가장 높은 빈도를 기록했으므로 결과의 맨 앞에 위치합니다. 'durable'은 두 개의 문장(인덱스 0, 1)에 등장했고, 'strong'은 한 개의 문장(인덱스 1)에만 등장했습니다. 이처럼 구문들은 등장 횟수가 많은 순서대로 배치됩니다.
해결 접근 방법
이 문제는 다음 단계를 거쳐 해결할 수 있습니다.
- 구문별 등장 횟수를 저장할 딕셔너리(
cnt)를 생성합니다. phrases의 모든 구문을 딕셔너리에 넣고 초기값을 0으로 설정합니다.sentences의 각 문장에 대해 다음을 반복합니다.- 문장을 공백 기준으로 분할해 단어 리스트(
p)를 만듭니다. - 단어 리스트로 집합(
s)을 생성해 중복을 제거합니다. - 집합의 각 단어가 딕셔너리에 존재하면 해당 카운트를 1 증가시킵니다.
- 문장을 공백 기준으로 분할해 단어 리스트(
- 딕셔너리의 각 항목으로 (구문, 등장 횟수) 쌍을 담은 리스트(
res)를 만듭니다. - 등장 횟수를 기준으로 내림차순 정렬합니다. 동률일 때는 원래
phrases리스트에서의 순서를 유지합니다. - 카운트 값을 제외하고 구문만 담은 리스트를 반환합니다.
여기서 집합(set)을 사용하는 것이 중요합니다. 같은 문장 안에서 동일한 단어가 여러 번 반복되더라도 한 번만 계산되도록 하기 위함입니다. 즉, "문장당 한 번"이라는 기준으로 등장 여부를 판단하게 됩니다.
예제 코드
위 알고리즘을 파이썬으로 구현하면 다음과 같습니다.
def solve(phrases, sentences):
cnt = {}
for feature in phrases:
cnt[feature] = 0
for response in sentences:
p = response.split()
s = set(p)
for i in s:
if i in cnt:
cnt[i] += 1
res = [[k, cnt[k]] for k in cnt]
res.sort(key = lambda x:(-x[1], phrases.index(x[0])))
return [i[0] for i in res]
print(solve(['strong', 'durable', 'efficient'], ['the product is durable and efficient', 'strong and durable', 'it is efficient', 'like it because it is efficient']))
입력
['strong', 'durable', 'efficient'],
['the product is durable and efficient', 'strong and durable', 'it is efficient', 'like it because it is efficient']
출력
['efficient', 'durable', 'strong']
핵심 로직 살펴보기
정렬 부분의 핵심은 key=lambda x: (-x[1], phrases.index(x[0]))입니다. 등장 횟수에 음수를 붙여 내림차순 정렬 효과를 얻고, 횟수가 같은 구문끼리는 원래 phrases 리스트에서의 인덱스 순서대로 배치되므로 입력 순서의 안정성이 보장됩니다.
시간 복잡도를 살펴보면, 모든 문장을 순회하며 단어를 검사하는 과정이 전체 문장 수 N과 평균 단어 수 L에 비례해 O(N × L) 수준이며, 마지막 정렬 단계에서 구문 수 K에 대해 O(K log K)가 추가됩니다.