Partition Labels
소문자로 이루어진 문자열 s가 주어집니다. 각 문자가 하나의 부분에만 나타나도록 문자열을 가능한 한 많은 연속된 부분으로 나누세요. 어떤 문자가 한 부분에 나타난다면, 그 문자의 모든 출현도 그 부분에 있어야 합니다. 왼쪽에서 오른쪽 순서대로 각 부분의 길이를 반환하세요.
함수
- sstring
- 잘라낼 문자열, 소문자만
- 반환값integer-array
- 왼쪽에서 오른쪽으로 각 부분의 길이
제약 조건
1 ≤ s.length ≤ 5 × 104s에는 소문자 영어 문자만 포함됩니다.- 각 부분은 순서를 유지하며 함께
s전체를 이루므로, 길이를 모두 더하면s.length가 됩니다.
예제
- 입력
- s = "abacdcefe"
- 출력
- [3, 3, 3]
- 설명
- a는 0과 2에, c는 3과 5에, e는 6과 8에 있으므로, 분할 지점은
aba뒤와cdc뒤에 옵니다. 각 부분은 같은 문자로 시작하고 끝나므로 더 이상 자를 수 없습니다.
- 입력
- s = "codingisfun"
- 출력
- [1, 1, 1, 8]
- 설명
- 문자 c, o, d는 각각 한 번씩 나타나므로 각각 단독으로 있습니다. 인덱스 3의 i는 인덱스 6에 복사본이 있고, 인덱스 4의 n은 문자열의 끝인 인덱스 10에 복사본이 있으므로, 인덱스 3부터 끝까지가 8개 문자의 한 부분입니다.
- 입력
- s = "zebraz"
- 출력
- [6]
- 설명
- 첫 번째 문자인 z가 마지막 문자로 되돌아오므로 문자열 전체가 한 부분으로 유지되어야 합니다.
제출 시 숨은 테스트 +14개
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
첫 번째 부분에는
s[0]이 포함되어야 합니다. 최소한 오른쪽으로 얼마나 멀리까지 도달해야 할까요?문자를 담는 부분은 해당 문자의 마지막 복사본까지 도달해야 하며, 그 과정에서 포함하는 각 문자는 범위를 더 늘릴 수 있습니다. 먼저 모든 문자의 마지막 위치를 기록해 두면, 조회마다
O(1)의 비용이 듭니다.왼쪽에서 오른쪽으로 읽으면서
end를 유지하세요.end는 현재 부분에 있는 문자들의 마지막 위치 중 가장 큰 값입니다. 현재 위치가end와 같아지면 해당 부분의 문자는 그 뒤에 더 이상 나오지 않습니다. 그 위치에서 자르고, 길이를 기록한 다음 새 부분을 시작하세요.
풀이
자르는 위치의 양쪽에 같은 문자가 나타나지 않는 곳에서만 자를 수 있으며, 가장 좋은 답은 그런 모든 위치에서 자르는 것입니다. 문자열을 다시 훑으며 각 위치를 확인하면 시간 복잡도가 이차가 됩니다. 먼저 각 문자의 마지막 위치를 기록하고, 왼쪽에서 오른쪽으로 한 번만 훑으면 모든 자르는 위치를 찾을 수 있습니다. 각 구간은 그 안에 있는 모든 문자의 마지막 등장 위치까지 늘어나야 하기 때문입니다.
모든 빈칸을 테스트하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
서로 이웃한 문자 사이에는 n-1개의 간격이 있습니다. 간격을 기준으로 자르는 것은 양쪽에 같은 문자가 하나도 없을 때만 가능합니다. 자른 위치에서 문자가 나뉘면 두 부분에 걸쳐 나타나기 때문입니다. 자를 수 있는 모든 곳을 자르면 조각 수가 최대가 됩니다. 서로 이웃한 두 절단 지점 사이의 한 조각을 생각해 봅시다. 그 조각의 문자는 왼쪽 절단 지점의 왼쪽이나 오른쪽 절단 지점의 오른쪽에 나타나지 않으므로, 해당 문자의 모든 복사본이 조각 안에 있으며 유효한 조각입니다. 그리고 유효한 답은 자를 수 있는 간격에서만 자를 수 있으므로, 어떤 답도 조각 수가 더 많을 수 없습니다.
따라서 각 간격을 확인합니다. 간격의 왼쪽과 오른쪽에 있는 문자들을 모으고, 두 집합에 공통된 문자가 없으면 자릅니다. abacdcefe에서 aba 다음 간격의 왼쪽에는 a와 b가 있고, 오른쪽에는 c, d, e, f가 있습니다. 공통된 문자가 없으므로 자릅니다. ab 다음 간격은 양쪽에 a가 있으므로 자르지 않습니다.
각 확인 작업은 문자열 전체를 읽고, 간격은 n-1개이므로 문자 읽기 횟수는 대략 n²입니다. 문자가 50,000개라면 읽기 횟수가 2.5 × 10^9회가 되어 가장 큰 테스트에서는 너무 느립니다.
알고리즘
- 현재 부분이 시작되는 위치인
start = 0으로 설정합니다. - 1부터
n-1까지 각 간격cut(s[cut]바로 앞의 간격)에 대해s[0..cut-1]의 문자와s[cut..n-1]의 문자를 표시합니다. - 양쪽 모두에 표시된 문자가 없다면, 답에
cut-start를 더하고start = cut으로 설정합니다. - 반복문이 끝난 후 마지막 부분인
n-start를 더합니다.
def partitionLabels(s):
n = len(s)
sizes = []
start = 0 # where the current part begins
for cut in range(1, n): # the gap just before s[cut]
left = set(s[:cut])
right = set(s[cut:])
if not (left & right): # no letter on both sides: cut here
sizes.append(cut - start)
start = cut
sizes.append(n - start) # the last part has no gap after it
return sizes각 문자의 범위를 병합하기
핵심 아이디어
각 문자를 처음 나타나는 위치부터 마지막으로 나타나는 위치까지의 구간으로 생각해 보세요. 문자를 포함하는 부분은 그 구간 전체를 포함해야 합니다. 따라서 구간이 겹치는 두 문자는 같은 부분에 포함되어야 하고, 겹침은 퍼져 나갑니다. a가 b와 겹치고 b가 c와 겹치면 세 문자 모두 하나의 부분에 포함됩니다.
이것이 구간 병합 문제입니다. 한 번 순회하며 각 문자가 처음 나타나는 위치와 마지막으로 나타나는 위치를 기록하세요. 그런 다음 시작 위치 순서대로 구간을 살펴보고 겹치는 구간을 병합하세요. 병합된 각 블록이 하나의 부분이고, 블록 사이의 간격이 허용되는 분할 지점입니다. 정렬하지 않아도 구간을 시작 위치 순서대로 얻을 수 있습니다. 문자열을 다시 순회하면서 각 문자가 처음 나타나는 위치에 도달했을 때 그 문자의 구간을 가져오면 됩니다.
codingisfun에서 순서대로 나열한 구간은 c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] 및 u [9, 9]입니다. 처음 세 구간은 각각 독립적입니다. i부터는 모든 구간의 시작 위치가 n의 끝 위치인 10 이하이므로, 구간들이 [3, 10]으로 병합되어 8개의 문자를 포함하는 부분이 됩니다.
문자열에는 서로 다른 문자가 최대 26개 있으므로 구간도 최대 26개이고, 처음 위치와 마지막 위치를 저장하는 배열의 크기는 고정되어 있습니다.
알고리즘
s를 한 번 순회하면서 각 문자의 첫 번째 위치와 마지막 위치인first와last를 기록합니다.s를 다시 순회합니다. 위치i가 해당 문자의 첫 번째 위치라면, 그 문자의 구간[i, last]가 시작 위치 순서상 다음 구간입니다.- 구간이 현재 블록의
end뒤에서 시작하면 길이가end-start+1인 블록을 닫고,i에서 새 블록을 시작합니다. - 어느 경우든
end = max(end, last)로 설정합니다. - 마지막 블록을 닫고 길이들을 반환합니다.
def partitionLabels(s):
first, last = {}, {}
for i, c in enumerate(s):
first.setdefault(c, i)
last[c] = i
sizes = []
start = end = 0 # the block of merged spans being built
for i, c in enumerate(s):
if first[c] != i:
continue # take each letter's span once, at its first position
if i > end: # this span starts after the block: close the block
sizes.append(end - start + 1)
start = i
end = max(end, last[c])
sizes.append(end - start + 1)
return sizes각 부분을 마지막 글자까지 늘리세요
핵심 아이디어
첫 번째 위치들은 전혀 필요하지 않습니다. 문자열을 왼쪽에서 오른쪽으로 읽으며 현재 부분에서 어떤 문자든 마지막으로 나타나는 가장 먼 위치인 end를 유지합니다. i에서 문자를 읽을 때 그 문자의 마지막 등장 위치도 이 부분 안에 있어야 하므로, 더 멀리 있다면 end를 last[s[i]]로 늘립니다.
i가 end에 도달하면 이 부분에서 읽은 모든 문자의 마지막 등장 위치가 i 이하입니다. i 다음의 경계를 넘어가는 문자가 없으므로 그곳에서 분할할 수 있습니다. 길이가 end-start+1인 부분을 마무리하고, 다음 부분은 i+1에서 시작합니다.
왜 처음 가능한 지점에서 분할하는 것이 올바른 그리디 선택일까요? i가 end에 도달하기 전에는 해당 부분의 어떤 문자든 더 오른쪽에 다시 나타나므로, 더 일찍 분할할 수 없습니다. 또한 이 과정은 가능한 경계를 놓치지 않습니다. i 다음 경계를 넘어가는 문자가 없다면 해당 부분의 모든 문자는 i까지 끝나므로, 바로 그 지점에서 end는 i와 같습니다. 이 과정은 분할 가능한 경계에서 정확히 분할하므로 가능한 부분의 수가 최대가 됩니다.
abacdcefe에서 마지막 위치는 a가 2, b가 1, c가 5, d가 4, e가 8, f가 7입니다. a를 읽으면 end가 2가 되고, b를 읽어도 그대로 유지됩니다. i = 2에서 길이가 3인 부분이 마무리됩니다. c를 읽으면 end가 5가 되고, 5에서 해당 부분이 마무리되어 다시 길이가 3이 됩니다. e 부분은 8에서 마무리됩니다.
알고리즘
- 한 번 순회하면서 각 문자
c의 마지막 위치인last[c]를 크기 26의 배열에 저장합니다. start = 0과end = 0으로 설정합니다.- 각 위치
i에 대해end = max(end, last[s[i]])로 설정합니다. i == end이면 답에end-start+1을 더하고start = i+1로 설정합니다.- 길이들을 반환합니다.
def partitionLabels(s):
last = {c: i for i, c in enumerate(s)} # last position of each letter
sizes = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # the part must reach c's last copy
if i == end: # no letter of this part appears later
sizes.append(end - start + 1)
start = i + 1
return sizes
함정과 경계 사례
그리디 패스는 짧기 때문에, 버그는 어느 위치를 기준으로 비교하는지와 부분 문자열의 길이에 숨어 있습니다.
- 부분의
end가 아니라 현재 문자의 마지막 복사본에 도달했을 때 자르는 경우입니다.abcba에서 인덱스 2의 c는 c의 마지막 복사본이지만, a는 인덱스 4까지 이어지므로 그 위치에서 자르면 a와 b가 모두 나뉩니다. - 길이를 하나씩 잘못 계산하는 경우입니다.
start부터end까지 양쪽 끝을 포함하는 부분에는end-start+1개의 문자가 있습니다. - 길이가 아니라 자르는 위치를 반환하는 경우입니다.
abacdcefe의 답은[2, 5, 8]이 아니라[3, 3, 3]입니다. - 간격에서 자를 때 마지막 부분을 잊는 경우입니다. 마지막 부분 뒤에는 간격이 없으므로, 루프가 끝난 뒤
n-start를 한 번 더해야 합니다. - 서로 다른 문자마다 부분이 하나씩 생길 거라고 예상하는 경우입니다.
zebraz에는 서로 다른 문자가 다섯 개 있지만 부분은 하나뿐입니다. z들이 그 사이의 모든 문자를 하나로 묶기 때문입니다.
자주 묻는 질문4
Partition Labels의 시간 복잡도는 얼마인가요?
한 번의 순회로 각 문자의 마지막 위치를 기록하고 두 번째 순회로 잘라낼 위치를 정하므로 시간 복잡도는 O(n)입니다. 마지막 위치를 담은 표는 문자열 길이와 관계없이 26개의 항목으로 이루어져 있으므로, 결과를 제외한 추가 공간 복잡도는 O(1)입니다.
Partition Labels에서 탐욕적 접근 방식이 작동하는 이유는 무엇인가요?
현재 부분은 포함된 각 문자의 마지막 등장 위치까지 도달해야 하므로, end 이전에는 자를 수 없습니다. end에서는 해당 부분의 어떤 문자도 이후에 다시 나타나지 않으므로 자를 수 있으며, 그렇게 잘라도 나머지 문자열에는 아무런 문제가 없습니다. 따라서 이 과정에서는 자를 수 있는 모든 경계에서 자르고 그 외에는 자르지 않으며, 이는 어떤 답보다도 부분의 수가 많습니다.
Partition Labels는 구간 병합 문제인가요?
네, 다른 형태로 표현하면 그렇습니다. 각 문자는 처음 등장한 위치부터 마지막으로 등장한 위치까지의 구간을 차지하고, 겹치는 구간은 일부를 공유해야 하며, 이를 병합하면 정확히 그 부분들이 됩니다. 탐욕적 순회는 즉석에서 병합하는 것과 같습니다. end는 지금까지 병합된 블록의 오른쪽 끝입니다.
Partition Labels는 몇 개의 부분을 반환할 수 있나요?
1에서 26 사이입니다. 두 부분에 같은 문자가 나타날 수 없으므로, 각 부분에는 적어도 그 부분만의 문자가 하나 있어야 하며, 소문자는 총 26개뿐입니다. 모든 문자가 한 번씩 나오는 문자열은 길이가 1인 부분 26개를 만들고, 같은 문자로 시작하고 끝나는 문자열은 하나의 부분을 만듭니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def partitionLabels(s):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
s = "abacdcefe"
기대값
[3, 3, 3]