문제 보기 · Level 1 · 2025 카카오 하반기 1차 · 정답률 28% · 푼 사람 2,964명 (2026-09-30 기준)1
문제
공백으로 나뉜 단어들로 된 메시지와, 서로 겹치지 않는 스포 방지 구간 목록이 주어진다. 글자 하나라도 구간에 걸린 단어는 스포 방지 단어다. 구간을 왼쪽부터 하나씩 열 때 드러나는 스포 방지 단어가 다음 두 조건을 모두 만족하면 중요한 단어다.
- 스포 방지되지 않은 부분에 나온 적이 없다.
- 앞서 드러난 단어와 겹치지 않는다.
중요한 단어의 수를 돌려준다.
- 메시지 길이 ≤ 20,000
- 구간 최대 1,000개, 시작 위치 순으로 정렬됨
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 문자열 파싱과 정규 표현식: 메시지를 단어로 나누면서 각 단어의 시작·끝 위치도 함께 기억한다.
- 딕셔너리와 집합: “나온 적이 있나”를 집합으로 바로 확인한다.
1단계 · 작은 예로 손으로 풀기
메시지 "cat dog cat bird", 가린 구간은 dog의 d 한 글자와 bird 전체라고 하자.
- 단어와 가림 여부: cat(보임), dog(가림), cat(보임), bird(가림)
- 보이는 단어 모음: {cat}
- 가린 단어를 왼쪽부터 드러낸다:
- dog: 보이는 곳에 없고, 앞서 드러난 적 없음 → 중요 (1개)
- bird: 같은 이유로 중요 (2개)
답은 2다. dog는 글자 하나만 가려졌어도 스포 방지 단어다.
2단계 · 가장 단순한 방법과 그 속도
단어마다 모든 구간을 돌며 겹치는지 보면, 단어 약 1만 개 × 구간 1,000개 = 1,000만 번이다. 파이썬에서 1~2초라 아슬아슬하다. 글자마다 “가려졌나”를 먼저 표시해 두면, 단어마다 자기 글자만 보면 되어 메시지 길이만큼(2만 번)으로 줄어든다.
3단계 · 핵심 아이디어
- 글자 표시: 길이 n의 참·거짓 리스트
hidden에 구간의 글자를 모두 참으로 칠한다. 구간 길이의 합은 n을 넘지 않는다. 구간끼리 겹치지 않으니 합의 법칙으로 길이의 합이 칠한 글자 수와 같고, 칠한 글자는 모두 메시지 안에 있기 때문이다. - 단어 나누기: 메시지를 공백에서 끊으며 단어와 그 위치를 얻는다. 단어의 글자 중 하나라도 가려졌으면 스포 방지 단어다.
- 보이는 단어 집합: 가려지지 않은 단어들을 집합으로 모은다. 조건 1은 “이 집합에 없다”다. 메시지 어디(앞이든 뒤든)에 보이는 단어든 해당한다.
- 왼쪽부터 판정: 스포 방지 단어를 왼쪽부터 보며, 보이는 단어 집합에도 없고 앞서 드러난 단어 집합에도 없으면 센다. 판정한 단어는 중요하든 아니든 “드러난 단어”에 넣는다.
왜 왼쪽부터가 드러나는 순서인가? 단어는 모든 글자가 드러날 때 공개된다. 구간을 왼쪽부터 열고 단어는 이어진 글자라서, 왼쪽 단어가 오른쪽 단어보다 늦게 완전히 드러나는 일은 없다.
4단계 · 코드 흐름
hidden을 모두 거짓으로 만들고 구간의 글자를 참으로 칠한다.- 메시지를 한 번 훑으며 공백이나 끝에서 단어를 끊고, (단어, 가려졌나)를 모은다.
- 가려지지 않은 단어로 집합
normal을 만든다. - 가려진 단어를 차례로 보며
normal과seen(드러난 단어) 둘 다에 없으면 센다. 그리고seen에 넣는다. - 센 수를 돌려준다.
5단계 · 파이썬 코드
def solution(message, spoiler_ranges):
n = len(message)
hidden = [False] * n
for s, e in spoiler_ranges: # 끝 글자 e도 포함
for i in range(s, e + 1):
hidden[i] = True
words = [] # (단어, 가려졌나)
start = 0
for i in range(n + 1):
if i == n or message[i] == " ": # 공백이나 끝에서 단어가 끝난다
if i > start:
words.append((message[start:i], any(hidden[start:i])))
start = i + 1
normal = {w for w, h in words if not h} # 보이는 단어들
seen = set()
count = 0
for w, h in words:
if h:
if w not in normal and w not in seen:
count += 1
seen.add(w)
return count
any(hidden[start:i]): 단어의 글자 중 하나라도 참이면 참이다.for i in range(n + 1): 끝(i == n)도 한 번 더 돌아서 마지막 단어를 끊는다.{w for w, h in words if not h}: 집합 컴프리헨션이다. 가려지지 않은 단어만 모은다.
6단계 · 실행 추적
메시지 "here is muzi here is a secret message", 구간 [0, 3], [23, 28]
- [0, 3]은 첫 here, [23, 28]은 secret을 가린다.
- 보이는 단어: {is, muzi, here, a, message}
| 가린 단어 | 보이는 곳에 있나 | 앞서 드러났나 | 중요? | seen |
|---|---|---|---|---|
| here | 있음 (4번째 단어) | 아니오 | {here} | |
| secret | 없음 | 없음 | 예 | {here, secret} |
답은 1이다. 첫 here는 뒤에 보이는 here가 있어서 중요하지 않다.
7단계 · 복잡도와 흔한 실수
메시지를 두 번 훑고 구간 글자를 한 번씩 칠하니 \(O(n)\)이다.
- 단어의 일부만 가려진 경우를 스포 방지 단어로 치지 않는다.
- “보이는 부분에 나온 적”을 앞쪽만 본다. 뒤에 나오는 보이는 단어도 해당한다.
- 중요하지 않다고 판정된 단어를
seen에 넣지 않는다. 조건 2는 “앞서 드러난 모든 단어”다.
검증: 문제의 예시 2개를 통과했고, 무작위 메시지 3,000개에서 “구간을 하나씩 열며 모든 글자가 드러난 단어를 그때그때 판정하는” 문제 문장 그대로의 느린 풀이와 결과가 같았다 — 06_pg468370_p1.py