[프로그래머스] 2025 카카오 하반기 1차 중요한 단어를 스포 방지 - Python

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/468370?language=python3

프로그래머스

 

아이디어

---

이 문제는 주어진 message에서 단어들을 확인한 뒤,

스포일러 구간에 포함되는 단어 중 진짜로 가려야 할 중요한 단어의 개수를 구하는 문제이다.

 

전체 흐름은 다음과 같이 잡았다.

 

1. 문자열에서 각 단어의 시작 인덱스와 끝 인덱스를 구한다.
2. 각 단어가 스포일러 구간과 겹치는지 확인한다.
3. 스포일러 구간과 겹치지 않는 단어는 일반 단어로 저장한다.
4. 스포일러 구간과 겹치는 단어는 후보 단어로 저장한다.
5. 후보 단어 중 일반 구간에도 등장한 단어는 제외한다.
6. 남은 단어들을 중복 없이 세어 정답을 구한다.

단어들을 split() 해서 저장하는 것이 아니라, 

인덱스를 하나씩 늘려가면서 시작과 끝, 단어를 다른 배열에 저장하는 것이 핵심 요소였던 것 같다.

 

전체 코드

---

'''
전체 프로세스

1. 단어의 시작과 끝 인덱스 구하기 (start, end)
2. 스포 구간과 해당 단어가 겹치는지 확인
    1. 겹치면 스포 방지 단어
    2. 안겹치면 일반 구간 단어
3. 스포 단어 중
    1. 일반 단어와 겹치는지 확인
    2. 이전에 나온 스포 방지 단어인지 확인 (set())
4. 최종 결과 return
'''

def solution(message, spoiler_ranges):
    
    # 단어 인덱스 구하기
    words = []
    i = 0
    
    while i < len(message):
        if message[i] == ' ':
            i += 1
            continue
            
        start = i
        while i < len(message) and message[i] != ' ':
            i += 1
        end = i - 1
        
        word = message[start: end + 1]
        words.append((start, end, word))
    
    normal_word = set()
    spoiler_words = [[] for _ in range(len(spoiler_ranges))]
    
    # 각 단어가 스포 구간과 겹치는지 확인
    for start, end, word in words:
        spoiler_index = 0
        
        first = -1
        last = -1
        for spoiler in spoiler_ranges:
            a, b = spoiler
            
            if b < start:
                continue
            if a > end:
                break
        
            if first == -1:
                first = spoiler_index
            last = spoiler_index
            spoiler_index += 1
        
        if first == -1:
            normal_word.add(word)
        else:
            spoiler_words[last].append(word)
    
    # 중요한 단어 판별
    important_word = set()
    
    for spoiler_word in spoiler_words:
        for word in spoiler_word:
            if word not in normal_word:
                important_word.add(word)
    
    return len(important_word)

 

단어의 시작, 끝 인덱스 구하기

words = []
i = 0

while i < len(message):
    if message[i] == ' ':
        i += 1
        continue
        
    start = i
    while i < len(message) and message[i] != ' ':
        i += 1
    end = i - 1
    
    word = message[start: end + 1]
    words.append((start, end, word))

 

먼저 message를 직접 순회하면서 단어를 분리했다.

 

단순히 split()만 사용하면 단어의 위치 정보를 잃어버리기 때문에,

각 단어의

• 시작 인덱스
• 끝 인덱스
• 실제 단어

를 함께 저장했다.

 

일반 단어와 스포일러 단어 저장 공간 만들기

normal_word = set()
spoiler_words = [[] for _ in range(len(spoiler_ranges))]

 

normal_word는 스포일러 구간과 겹치지 않는 일반 단어를 저장한다.

 

set을 사용한 이유는

나중에 특정 단어가 일반 구간에도 등장했는지 빠르게 확인하기 위해서 사용했다. => in 키워드 사용하면 O(1)

 

spoiler_words는 스포일러 구간과 겹친 단어들을 저장하는 배열이다.

 

단어와 스포일러 구간이 겹치는지 확인

for start, end, word in words:
    spoiler_index = 0
    
    first = -1
    last = -1
    for spoiler in spoiler_ranges:
        a, b = spoiler
        
        if b < start:
            continue
        if a > end:
            break
    
        if first == -1:
            first = spoiler_index
        last = spoiler_index
        spoiler_index += 1

 

각 단어마다 모든 스포일러 구간을 확인하면서

단어의 범위와 스포일러 구간이 겹치는지 판단한다.

 

두 구간이 겹치지 않는 경우는 

b < start -> 스포일러 구간이 단어보다 왼쪽일 때,

a > end -> 스포일러 구간이 단어보다 오른쪽일 때,

 

이 두 경우가 아니면 단어는 무조건 겹친다.

 

first와 last로 구분한 이유는, 

한 단어가 여러 스포일러 구간으로 나누어지는 경우 마지막 스포일러 구간을 기준으로

단어를 저장하기 위해서이다.

 

일반 단어 / 스포일러 단어 분리

if first == -1:
    normal_word.add(word)
else:
    spoiler_words[last].append(word)

스포일러 구간과 한 번도 겹치지 않았다면 

해당 단어는 normal_word (일반 단어)에 저장하고

 

겹쳤다면, 마지막 구간을 기준으로 단어를 저장했다.

 

중요한 단어 판별

important_word = set()

for spoiler_word in spoiler_words:
    for word in spoiler_word:
        if word not in normal_word:
            important_word.add(word)

일반 구간 단어와 겹치는 단어를 제외하고, 

중복된 스포일러 단어를 제외한 후 중요한 단어 리스트에 저장한다.

 

최종적으로 중요한 단어 개수를 반환하면 끝.