[프로그래머스] 중요한 단어를 스포 방지

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/468370

 

2. 코드

python 1

def solution(message, spoiler_ranges):
    answer = 0
    words = message.split(" ")
    words_index_list = []
    index = 0
    general_word = set()
    spoiler_word = set()
    
    # (start, end, word) 형태로 저장
    for word in words:
        start = index 
        end = index + len(word) - 1
        words_index_list.append((start, end, word))
        index = index + len(word) + 1

    # general_word인지 판별
    for word_start, word_end, word in words_index_list:
        is_spoiler = False
        
        for spoiler_start, spoiler_end in spoiler_ranges:
            # spoiler 범위인 경우
            if not (spoiler_end < word_start or spoiler_start > word_end):
                is_spoiler = True
                break
        
        if not is_spoiler:
                general_word.add(word)

    # spoiler_word인지 판별
    for word_start, word_end, word in words_index_list:
        is_spoiler = False
        
        for spoiler_start, spoiler_end in spoiler_ranges:
            # spoiler 범위인 경우
            if not (spoiler_end < word_start or spoiler_start > word_end):
                is_spoiler = True
                break
        
        if is_spoiler and word not in general_word:
            spoiler_word.add(word)
            
    return len(spoiler_word)

풀이

1. (start, end, word) 형태로 단어의 시작과 끝의 위치와 단어를 저장
2. 각 단어가 스포일러 구간에 포함되는지 확인
   1. spoiler_ranges가 아니라면 → 일반 단어로 설정
3. 스포일러 단어에 포함이 되고 일반 단어에 없다면 → 스포 방지 중요한 단어로 설정
4. 최종 스포 방지 중요한 단어의 개수 출력

 

python 2

def solution(message, spoiler_ranges):
    words = message.split(" ")
    words_index_list = []
    index = 0
    general_word = set()
    spoiler_word = set()
    
    # (start, end, word) 형태로 저장
    for word in words:
        word_start = index 
        word_end = index + len(word) - 1
        
        is_spoiler = False
        
        for spoiler_start, spoiler_end in spoiler_ranges:
            # spoiler 범위인 경우
            if not (spoiler_end < word_start or spoiler_start > word_end):
                is_spoiler = True
                break
                 
        
        words_index_list.append((word_start, word_end, word, is_spoiler))
        
        index += len(word) + 1
        
    # general_word 판별
    for _, _, word, is_spoiler in words_index_list:
        if not is_spoiler:
            general_word.add(word)
    
    # spoiler_word 판별
    for _, _, word, is_spoiler in words_index_list:
        if is_spoiler:
            if word in general_word:
                continue
        
            spoiler_word.add(word)

    return len(spoiler_word)

 

3. 메모

• 문자열을 활용한 구현 문제
• 시간 복잡도 : O(W×S)
  • W : 단어 개수
  • S : spoiler_ranges
• python 1에서는 spoiler의 범위를 2번 체크를 하여 중요 스포 단어 인지를 확인
• python 2에서는 **(start, end, word, is_spoiler)**로 저장하여 스포일러 여부를 한번만 계산
• 일반 단어와 중요한 스포 단어의 중복 여부는 Set을 활용하여 관리
• 단어 구간과 스포일러 구간이 한 글자라도 겹치는지 판별하는 것이 핵심
• 문제에서 말한 조건을 잘 확인하고 구현해야 함