프로그래머스

프로그래머스 중요한 단어를 스포 방지 풀이: 구간 처리와 해시

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

문자열 메시지의 일부 구간이 스포일러로 가려져 있습니다. 스포일러 구간을 메시지 왼쪽부터 하나씩 공개할 때, 다음 조건을 모두 만족하는 단어의 개수를 구해야 합니다.

  1. 단어의 문자 중 하나 이상이 스포일러 구간에 포함되어야 합니다.
  2. 같은 단어가 스포일러가 아닌 일반 영역에 등장한 적이 없어야 합니다.
  3. 이전에 공개된 스포일러 단어와 중복되지 않아야 합니다.
  4. 한 구간을 공개했을 때 여러 단어가 함께 공개되면 왼쪽 단어부터 판정합니다.

스포일러 구간은 서로 겹치지 않고 시작 위치 기준으로 정렬되어 있습니다. 메시지 길이는 최대 20,000이고 구간은 최대 1,000개이므로, 단어마다 모든 문자와 모든 구간을 직접 비교해도 동작할 수 있지만 구간 위치를 효율적으로 찾아두는 편이 안전합니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

단어의 문자 구간 만들기

공백을 기준으로 단어를 나누되, 각 단어의 시작 인덱스와 끝 인덱스를 함께 저장합니다. 예를 들어 메시지가 my phone number라면 단어별로 다음과 같은 구간을 얻습니다.

my     [0, 1]
phone  [3, 7]
number [9, 14]

스포일러 구간 [start, end]와 단어 구간 [left, right]가 겹치는 조건은 다음과 같습니다.

start <= right and left <= end

이분 탐색으로 겹치는 구간 찾기

스포일러 구간은 정렬되어 있으므로 시작 위치 배열과 끝 위치 배열을 따로 만들 수 있습니다.

  • 단어의 끝 이상으로 끝나는 첫 스포일러 구간을 찾습니다.
  • 단어의 끝 이하에서 시작하는 마지막 스포일러 구간을 찾습니다.
  • 두 위치가 유효하면 해당 단어는 스포일러 단어입니다.

단어가 여러 스포일러 구간에 걸쳐 있다면, 마지막으로 겹치는 구간이 공개되어야 단어 전체가 공개됩니다. 따라서 각 스포일러 단어에 last_range를 기록합니다.

해시 집합으로 일반 단어와 중복 관리

먼저 스포일러가 아닌 영역에 등장한 단어를 normal_words 집합에 넣습니다. 이후 공개 순서에 따라 스포일러 단어를 확인할 때 다음을 검사합니다.

  • normal_words에 있으면 중요한 단어가 아닙니다.
  • 이미 처리한 단어 집합에 있으면 중복이므로 세지 않습니다.
  • 둘 다 아니면 결과에 추가하고 처리 집합에 넣습니다.

스포일러 단어를 (마지막 공개 구간 번호, 단어 시작 위치) 기준으로 정렬하면, 같은 구간에서 여러 단어가 공개되는 경우에도 왼쪽부터 자연스럽게 처리할 수 있습니다.

복잡도

단어 수를 N, 스포일러 구간 수를 M이라고 하면 단어마다 이분 탐색을 하므로 전체 시간 복잡도는 O(N log M + N log N)입니다. 단어 구간과 집합, 이벤트 목록을 저장하는 공간 복잡도는 O(N + M)입니다.

핵심 관찰

단어가 스포일러 구간과 한 번이라도 겹친다는 사실만으로는 공개 시점을 정할 수 없습니다. 단어의 마지막 겹침 구간이 공개되어야 단어 전체가 드러나므로 그 구간 번호만 저장하면 됩니다. 일반 영역에 같은 단어가 있으면 공개 순서와 관계없이 제외되므로 집합으로 먼저 관리합니다.

오답 접근과 반례

단어와 겹치는 첫 번째 스포일러 구간을 공개 시점으로 사용하면 틀립니다. 한 단어가 구간 1과 구간 3에 걸쳐 있다면 구간 1 공개 때는 아직 일부가 가려져 있으므로 세면 안 됩니다. 따라서 첫 구간이 아니라 마지막 구간을 기준으로 정렬해야 합니다.

3. 문제 해결 코드 (Python)

from bisect import bisect_left


def solution(message, spoiler_ranges):
    words = []
    index = 0

    # 단어와 단어가 차지하는 [시작, 끝] 인덱스를 저장합니다.
    for word in message.split():
        start = message.find(word, index)
        end = start + len(word) - 1
        words.append((word, start, end))
        index = end + 1

    starts = [start for start, _ in spoiler_ranges]
    ends = [end for _, end in spoiler_ranges]

    def overlapping_range(left, right):
        first = bisect_left(ends, left)
        last = bisect_left(starts, right + 1) - 1
        if first > last:
            return None
        return first, last

    normal_words = set()
    spoiler_words = []

    for word, left, right in words:
        overlap = overlapping_range(left, right)
        if overlap is None:
            normal_words.add(word)
        else:
            _, last_range = overlap
            spoiler_words.append((last_range, left, word))

    # 같은 구간에서 공개되는 단어는 왼쪽부터 처리합니다.
    spoiler_words.sort(key=lambda item: (item[0], item[1]))

    seen = set(normal_words)
    answer = 0

    for _, _, word in spoiler_words:
        if word not in seen:
            answer += 1
            seen.add(word)

    return answer

구현 포인트

  • message.find(word, index)를 사용해 단어의 실제 문자 인덱스를 유지합니다.
  • 스포일러 구간은 포함 범위이므로 끝 위치 비교에 right + 1을 사용합니다.
  • 한 단어가 여러 구간과 겹치면 가장 마지막 구간이 공개된 시점에 판정합니다.
  • seen에 일반 단어를 먼저 넣어, 일반 영역에 한 번이라도 등장한 단어를 제외합니다.
  • seen은 중요한 단어로 이미 센 스포일러 단어도 기억해 중복 카운트를 막습니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 대체로 단어의 시작·끝 인덱스를 계산한 뒤 스포일러 구간과 겹치는지 확인하고, 일반 영역의 단어와 공개된 단어를 집합으로 관리하는 방식을 사용합니다.

  • 프로그래머스 공식 문제 페이지는 단어 일부만 스포일러에 포함되어도 단어 전체가 스포일러 단어가 된다는 조건과, 여러 구간이 한 단어를 가릴 수 있다는 조건을 제시합니다.
  • eeeunsong의 Python 풀이는 스포일러 구간과 겹치는 단어의 남은 공개 상태를 관리하면서 마지막 구간 공개 시점을 판정하는 접근을 설명합니다.

이 글의 풀이는 같은 집합 기반 아이디어를 사용하지만, 정렬된 스포일러 구간에서 단어와 겹치는 첫 구간과 마지막 구간을 이분 탐색으로 찾습니다. 다른 풀이처럼 구간 내부의 모든 문자를 직접 마스킹하지 않아도 되며, 마지막 공개 구간 번호로 단어 공개 시점을 계산할 수 있다는 점이 차이입니다.

마무리

이 문제는 문자열을 단순히 split()하는 것보다 각 단어가 메시지에서 어느 위치를 차지하는지 관리하는 것이 핵심입니다. 단어 구간과 스포일러 구간의 관계를 먼저 정리하고, 해시 집합으로 일반 단어와 중복을 관리하면 조건을 순서대로 깔끔하게 처리할 수 있습니다.

#해시#프로그래머스#난이도 2