프로그래머스

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

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

단어 구간과 스포일러 구간을 관리하고 해시와 이분 탐색을 함께 사용해야 하므로 Level 3으로 판단한다.

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은 중요한 단어로 이미 센 스포일러 단어도 기억해 중복 카운트를 막는다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 스포일러에만 나오는 단어와 일반 영역에도 등장하는 단어를 구분할 수 있다.

assert solution("red blue", [[0, 2]]) == 1
assert solution("red red", [[0, 2]]) == 0

4. 참고 풀이 비교

  • eeeunsong의 Python 풀이는 스포일러 구간과 겹치는 단어의 남은 공개 상태를 관리하면서 마지막 구간 공개 시점을 판정하는 접근을 설명한다.

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

마무리

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

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