문제 보기 · Level 5 · 2025 프로그래머스 코드챌린지 본선 · 정답률 1% · 푼 사람 152명 (2026-09-30 기준)1
문제
소문자 문자열 s가 처음에는 문자열 하나다. 문자마다 처음 자리를 번호로 쓴다(1번부터). 같은 문자열 안의 문자는 늘 번호순이고, 길이가 0이 된 문자열은 사라진다. 쿼리 다섯 가지를 차례로 한다.
1 x y: x번과 y번 문자가 같은 문자열에 있으면 “YES”, 아니면 “NO”를 결과에 넣는다.2 x word: 새 빈 문자열을 만든다. x번 문자가 든 문자열에서 word에 든 알파벳을 모두 새 문자열로 옮긴다.3 x y word: 새 빈 문자열을 만든다. 어느 문자열에 있든, x ~ y번 문자 가운데 word에 든 알파벳을 모두 새 문자열로 옮긴다.4 x y: x번 문자의 문자열과 y번 문자의 문자열을 합친다. 먼저 만들어진 문자열이 남고, 늦게 만들어진 쪽이 사라진다.-
5: 마지막에 한 번 온다. 남은 문자열마다 “a 3 b 2 e 2”처럼 알파벳과 개수를 사전 순으로 적어, 만들어진 순서대로 결과에 넣는다. - s 길이 1 ~ 100,000, 쿼리 1 ~ 200,000개, word 길이 1 ~ 26
풀이
막히면 한 단계씩 펼친다.
필요한 개념
쿼리는 늘 “글자 단위”로 문자를 옮긴다. 그래서 글자마다 따로 본다. 문자열을 합치는 4번은 유니온 파인드로, 번호 범위를 다루는 3번과 “이 문자가 어느 무리인가”는 이분 탐색으로 한다.
문자열들은 문자 1 ~ n을 겹치지 않게 나눈 분할이다. 1번은 “같은 조각인가”를 묻고, 4번은 조각을 합치고, 2·3번은 조각에서 문자를 떼어 새 조각을 만든다(3번은 여러 조각에서 뗀다). 유니온 파인드는 합치기만 할 수 있어서, 떼어 내기에는 다른 장치가 필요하다.
1단계 · 작은 예로 손으로 풀기
s = “abababab”(1 ~ 8번)이다.
| 쿼리 | 결과 | 쿼리 뒤의 문자열 (문자열 번호: 문자 번호) |
|---|---|---|
| 처음 | 0: 1 ~ 8 | |
| 3 2 6 ab | 0: 1, 7, 8 · 1: 2, 3, 4, 5, 6 | |
| 1 1 3 | NO | |
| 2 4 a | 0: 1, 7, 8 · 1: 2, 4, 6 · 2: 3, 5 | |
| 1 3 5 | YES | |
| 4 7 3 | 0: 1, 3, 5, 7, 8 · 1: 2, 4, 6 (2가 0에 합쳐진다) | |
| 1 3 7 | YES | |
| 5 | “a 4 b 1”, “b 3” |
2번은 “문자열 하나의 글자 하나”를 통째로 옮긴다. 3번은 “번호 범위 하나의 글자 하나”를 옮긴다. 4번은 문자열 둘의 모든 글자를 합친다.
2단계 · 가장 단순한 방법과 그 속도
문자마다 속한 문자열 번호를 적어 두고 그대로 따라 한다. 2, 3, 4번 쿼리마다 문자 10만 개를 훑으면 쿼리 20만 개에 200억 번이다. 어림없다.
3단계 · 핵심 아이디어
- 글자마다 번호 목록: 글자 c인 문자의 번호를 커지는 순으로 모아 pos[c]에 둔다. 번호 x ~ y인 c는 pos[c] 안에서 이어진 한 덩어리 lo ~ hi다. 이분 탐색 두 번으로 찾는다.
- 꼬리표: 문자마다 문자열 번호를 적으면 옮길 때마다 다 고쳐야 한다. 대신 함께 움직이는 문자 무리에 꼬리표(tag)를 하나 붙이고, 꼬리표마다 주인 문자열만 적는다. 문자열마다 글자마다 대표 꼬리표가 하나씩 있다(cur[문자열][글자]).
- 2번 = 꼬리표 넘기기: 문자열 S의 글자 c를 통째로 옮기려면 S의 c 꼬리표 주인을 새 문자열로 바꾸면 된다. 문자는 하나도 건드리지 않는다.
- 4번 = 꼬리표 잇기: 글자마다 늦게 생긴 쪽 꼬리표를 먼저 생긴 쪽 꼬리표 밑에 잇는다(union 연산). 문자의 진짜 문자열은 꼬리표의 뿌리를 찾아(find) 그 주인으로 안다.
- 3번 = 구간 덮기: 글자마다 pos[c]의 자리들을 “같은 꼬리표가 이어지는 구간”으로 나눠 둔다. lo ~ hi를 새 꼬리표 하나짜리 구간으로 덮는다. lo 앞과 hi 뒤에서 구간을 자르고, 그 사이 구간 시작들을 지운다. 한 번에 글자마다 구간이 많아야 2개 늘고, 지우는 구간은 전에 만든 것이라 다 합쳐도 만든 수를 넘지 않는다.
- 1번: 문자 번호 → 글자 c와 pos[c] 안의 자리 → 그 자리가 든 구간(이분 탐색) → 꼬리표 → 뿌리 → 주인 문자열. 두 문자의 주인이 같으면 YES다.
- 5번: 글자마다 구간을 훑어 구간 길이를 주인 문자열에 더한다. 문자열 번호가 곧 만들어진 순서다. 개수가 0인 문자열은 사라진 것이라 적지 않는다.
4단계 · 코드 흐름
- pos[c], 문자 번호 → (글자, 자리)를 만든다. 글자마다 처음 꼬리표를 문자열 0의 것으로 하나 만들고, 구간은 전체 하나다.
- 1번: string_of(x) == string_of(y)를 본다.
- 2번: S = string_of(x). 새 문자열을 만들고, word의 글자마다 cur[S]에서 꼬리표를 꺼내 주인을 새 문자열로 바꾼다.
- 3번: 새 문자열을 만든다. word의 글자마다 lo, hi를 찾고, 비어 있지 않으면 새 꼬리표를 만들어 lo ~ hi 구간을 덮는다.
- 4번: 두 문자열이 다르면, 늦은 쪽의 글자별 꼬리표를 먼저 생긴 쪽 꼬리표 밑에 잇는다. 먼저 생긴 쪽에 그 글자가 없으면 꼬리표 주인만 바꾼다.
- 5번: 구간 길이를 문자열별로 세어 번호순으로 적는다.
5단계 · 파이썬 코드
from bisect import bisect_left, bisect_right
def solution(s, query):
n = len(s)
pos = [[] for _ in range(26)] # 글자마다 그 글자인 문자 번호들
letter, idx = [0] * (n + 1), [0] * (n + 1)
for i, ch in enumerate(s, 1):
c = ord(ch) - 97
letter[i], idx[i] = c, len(pos[c])
pos[c].append(i)
parent, owner = [], [] # 꼬리표의 유니온 파인드, 뿌리 꼬리표 → 문자열
def new_tag(sid):
parent.append(len(parent))
owner.append(sid)
return len(parent) - 1
def find(v):
root = v
while parent[root] != root:
root = parent[root]
while parent[v] != root:
parent[v], v = root, parent[v]
return root
cur = [{}] # 문자열마다: 글자 → 대표 꼬리표
starts = [[] for _ in range(26)] # 글자마다: 구간이 시작하는 자리
tags = [[] for _ in range(26)] # 글자마다: 구간의 꼬리표
for c in range(26):
if pos[c]:
t = new_tag(0)
cur[0][c] = t
starts[c], tags[c] = [0], [t]
def string_of(i):
c = letter[i]
j = bisect_right(starts[c], idx[i]) - 1
return owner[find(tags[c][j])]
result = []
for q in query:
p = q.split()
if p[0] == "1":
result.append("YES" if string_of(int(p[1])) == string_of(int(p[2])) else "NO")
elif p[0] == "2":
src = cur[string_of(int(p[1]))]
new = len(cur)
cur.append({})
for c in {ord(ch) - 97 for ch in p[2]}:
t = src.pop(c, None)
if t is not None: # 꼬리표를 통째로 넘긴다
owner[t] = new
cur[new][c] = t
elif p[0] == "3":
x, y = int(p[1]), int(p[2])
new = len(cur)
cur.append({})
for c in {ord(ch) - 97 for ch in p[3]}:
lo = bisect_left(pos[c], x)
hi = bisect_right(pos[c], y) - 1
if lo > hi:
continue
t = new_tag(new)
cur[new][c] = t
st, tg = starts[c], tags[c]
j = bisect_right(st, lo) - 1
if st[j] != lo: # lo 앞에서 자른다
st.insert(j + 1, lo)
tg.insert(j + 1, tg[j])
j += 1
if hi + 1 < len(pos[c]): # hi 뒤에서 자른다
j2 = bisect_right(st, hi + 1) - 1
if st[j2] != hi + 1:
st.insert(j2 + 1, hi + 1)
tg.insert(j2 + 1, tg[j2])
e = bisect_right(st, hi)
del st[j + 1:e], tg[j + 1:e] # lo ~ hi를 구간 하나로
tg[j] = t
elif p[0] == "4":
sx, sy = string_of(int(p[1])), string_of(int(p[2]))
if sx == sy:
continue
old, young = min(sx, sy), max(sx, sy)
dst = cur[old]
for c, t in cur[young].items():
if c in dst:
parent[t] = dst[c] # 같은 글자 꼬리표끼리 잇는다
else:
owner[t] = old
dst[c] = t
cur[young] = {}
else: # 5
cnt = {}
for c in range(26):
st, tg, size = starts[c], tags[c], len(pos[c])
for j in range(len(st)):
length = (st[j + 1] if j + 1 < len(st) else size) - st[j]
row = cnt.setdefault(owner[find(tg[j])], [0] * 26)
row[c] += length
for sid in sorted(cnt):
row = cnt[sid]
if any(row):
result.append(" ".join(f"{chr(97 + c)} {row[c]}" for c in range(26) if row[c]))
return result
starts[c]의 값은 문자 번호가 아니라 pos[c] 안의 자리다. 그래서 자리 j의 문자 번호는 pos[c][j]다.{ord(ch) - 97 for ch in p[3]}: word에 같은 글자가 여러 번 있어도 한 번만 처리한다.cur[young] = {}: 합쳐져 사라진 문자열은 대표 꼬리표가 없다. 그 꼬리표들은 이제 먼저 생긴 쪽 뿌리 밑에 있다.owner는 뿌리 꼬리표에서만 믿는다. 그래서 늘owner[find(t)]로 읽는다.
6단계 · 실행 추적
1단계의 예에서 pos[a] = [1, 3, 5, 7], pos[b] = [2, 4, 6, 8]이다. 구간을 (문자 번호들 → 주인 문자열)로 적는다.
| 쿼리 | a의 구간 | b의 구간 | 한 일 |
|---|---|---|---|
| 처음 | 1, 3, 5, 7 → 0 | 2, 4, 6, 8 → 0 | |
| 3 2 6 ab | 1 → 0 · 3, 5 → 1 · 7 → 0 | 2, 4, 6 → 1 · 8 → 0 | a는 양쪽에서 자르고, b는 뒤에서만 자른다 |
| 2 4 a | 1 → 0 · 3, 5 → 2 · 7 → 0 | 그대로 | 문자열 1의 a 꼬리표 주인을 2로 바꾼다 |
| 4 7 3 | 1 → 0 · 3, 5 → 0 · 7 → 0 | 그대로 | 문자열 2의 a 꼬리표를 문자열 0의 a 꼬리표 밑에 잇는다 |
2번과 4번은 구간을 건드리지 않는다. 꼬리표의 주인과 뿌리만 바뀐다. 5번은 a 구간 셋(1 + 2 + 1 = 4개)과 b의 8번을 문자열 0에, b의 2, 4, 6번을 문자열 1에 센다. 그래서 “a 4 b 1”, “b 3”이다.
7단계 · 복잡도와 흔한 실수
1번은 이분 탐색과 find라 \(O(\log n)\)쯤이다. 2번과 4번은 글자 수(26) 만큼, 3번은 글자마다 이분 탐색 몇 번이다. 지우는 구간은 다 합쳐 만든 구간 수를 넘지 않는다. 파이썬 리스트의 insert와 del은 뒤쪽을 미는 비용이 있지만, 글자마다 구간 수가 그 글자의 문자 수를 넘지 않아 실제로는 빠르다. 글자 10만 개, 쿼리 20만 개로 재 보니 섞인 쿼리는 0.8초, 모든 쿼리가 26글자를 옮기는 3번이면 4 ~ 6초가 걸렸다. 채점 서버에서 이 시간이 제한 안인지는 확인하지 못했다.
- 3번을 “x번 문자가 든 문자열 안에서만” 옮긴다고 읽는다. 3번은 문자열과 상관없이 번호 x ~ y의 문자를 모두 본다.
- 4번에서 늘 x 쪽에 y 쪽을 붙인다. 먼저 만들어진 문자열이 남아야 5번의 순서가 맞는다.
- 5번에서 길이가 0인 문자열까지 적는다. 2번이나 3번으로 아무것도 옮겨지지 않은 문자열, 합쳐져 사라진 문자열은 빼야 한다.
- 2번에서 문자를 하나씩 옮긴다. 문자열 하나의 글자 하나는 꼬리표 하나라, 주인만 바꾸면 된다.
-
프로그래머스 스쿨, “문자열과 알파벳과 쿼리” (https://school.programmers.co.kr/learn/courses/30/lessons/389632), 2026-10-01 조회. ↩