문제 개요
소문자로만 이루어진 문자열 s가 주어졌을 때, 최대 한 글자를 삭제해서 s를 "유효한 문자열"로 바꿀 수 있는지 확인하는 것이 이번 문제의 목표입니다. 여기서 유효한 문자열이란, 문자열 안에 등장하는 모든 고유 문자의 빈도(등장 횟수)가 서로 같은 문자열을 뜻합니다.
예를 들어 입력이 s = "xyyzx"라면 결과는 True입니다. 'z' 하나만 삭제하면 문자열이 "xyyx"가 되고, x와 y가 각각 두 번씩 등장해 빈도가 일치하기 때문입니다.
접근 방법
풀이의 핵심은 각 문자의 등장 횟수를 먼저 계산한 뒤, 빈도 값들을 종류별로 묶어 상황을 판단하는 것입니다. 판정 규칙은 다음과 같습니다.
- 빈도가 이미 모두 같은 경우 → 삭제 없이 조건을 만족하므로 True
- 서로 다른 빈도가 3가지 이상 섞인 경우 → 단 한 번의 삭제로는 절대 맞출 수 없으므로 False
- 빈도가 1인 문자가 하나뿐인 경우 → 그 문자를 통째로 지우면 나머지 빈도가 일치하므로 True
- 공통 빈도보다 정확히 1 큰 빈도의 문자가 하나뿐인 경우 → 해당 문자 하나를 지우면 되므로 True
- 위 어느 경우에도 해당하지 않는 경우 → False
파이썬 구현 예제
size = 26
def solve(s):
# 각 알파벳의 등장 횟수를 저장할 배열
occurrence = [0] * size
for ch in s:
occurrence[ord(ch) - ord('a')] += 1
# 빈도 값별로 몇 개의 문자가 속하는지 집계
freq_count = {}
for f in occurrence:
if f != 0:
freq_count[f] = freq_count.get(f, 0) + 1
keys = list(freq_count.keys())
# 1) 모든 빈도가 이미 동일한 경우
if len(keys) == 1:
return True
# 2) 서로 다른 빈도가 3개 이상이면 한 번의 삭제로 해결 불가
if len(keys) > 2:
return False
f1, f2 = sorted(keys)
# 3) 빈도가 1인 문자가 하나뿐이라면 그 문자를 통째로 삭제
if f1 == 1 and freq_count[f1] == 1:
return True
# 4) 공통 빈도보다 1 많은 빈도를 가진 문자가 하나뿐이라면 하나를 삭제
if f2 == f1 + 1 and freq_count[f2] == 1:
return True
return False
s = "xyyzx"
print(solve(s))실행 결과
입력:
"xyyzx"출력:
True동작 과정 살펴보기
입력 "xyyzx"에서 각 문자의 등장 횟수는 x = 2회, y = 2회, z = 1회입니다. 이를 빈도 값별로 묶으면 {2: 2개의 문자, 1: 1개의 문자}가 됩니다. 빈도가 1인 문자(z)가 정확히 하나뿐이므로 세 번째 규칙에 따라 True가 반환됩니다.
시간·공간 복잡도
- 시간 복잡도: O(n) — 문자열을 한 번 순회하며 빈도를 계산하고, 이후에는 최대 26종의 빈도 그룹만 검사하면 됩니다.
- 공간 복잡도: O(1) — 알파벳은 소문자 26개로 고정되어 있어 추가 메모리 사용량이 일정합니다.