숫자로 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 여기서 멋진 부분 문자열(Awesome Substring)이란, 문자들의 순서를 원하는 만큼 서로 교환(swap)했을 때 회문(palindrome)으로 만들 수 있는 비어 있지 않은 부분 문자열을 의미합니다. 우리의 목표는 문자열 s에서 가장 긴 멋진 부분 문자열의 길이를 구하는 것입니다.
예를 들어 입력이 s = "4353526"이라면 출력은 5가 됩니다. 왜냐하면 "35352"가 가장 긴 멋진 부분 문자열이며, 이를 "35253"처럼 재배열하면 회문이 되기 때문입니다.
핵심 아이디어
어떤 문자열을 재배열하여 회문으로 만들 수 있는 조건은 간단합니다. 홀수 번 등장하는 숫자의 개수가 최대 1개여야 합니다. 따라서 각 숫자(0~9)의 등장 횟수가 홀수인지 짝수인지만 추적하면 되는데, 이때 비트마스크(bitmask)와 XOR 연산을 활용하면 효율적으로 처리할 수 있습니다.
- 10비트 정수 n을 사용하여, 각 비트는 해당 숫자의 등장 횟수가 홀수인지(1) 짝수인지(0)를 나타냅니다.
- 문자를 하나씩 처리할 때마다 n을 해당 숫자의 비트와 XOR하면 홀짝 상태가 자동으로 토글됩니다.
- 동일한 마스크 값이 이전에 나타난 적이 있다면, 두 위치 사이의 구간은 모든 숫자가 짝수 번 등장하므로 회문으로 만들 수 있습니다.
- 마스크 값 하나만 다른 경우(비트 하나만 차이)도 고려하면, 홀수 개인 숫자가 정확히 하나인 구간 역시 회문이 가능합니다.
알고리즘 단계
- n := 0 으로 초기화합니다.
- pos_map := {0: len(s)} — 마스크 값 0이 처음 등장한 위치를 문자열 길이로 저장한 맵입니다.
- max_len := 1 로 초기화합니다.
- i를 문자열 끝(len(s)-1)부터 0까지 거꾸로 반복합니다.
- n := n XOR (2^s[i]) 로 현재 숫자의 홀짝 상태를 갱신합니다.
- n이 pos_map에 존재하면, max_len := max(max_len, pos_map[n] - i) 로 갱신합니다.
- j를 0부터 9까지 반복하면서 m := n XOR (2^j) 를 계산하고, m이 pos_map에 존재하면 max_len := max(max_len, pos_map[m] - i) 로 갱신합니다.
- n이 pos_map에 없다면 pos_map[n] := i 로 저장합니다.
- 반복이 끝나면 max_len을 반환합니다.
Python 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(s):
n = 0
pos_map = {0: len(s)}
max_len = 1
for i in range(len(s)-1, -1, -1):
n = n ^ (1 << int(s[i]))
if n in pos_map:
max_len = max(max_len, pos_map[n] - i)
for j in range(10):
m = n ^ (1 << j)
if m in pos_map:
max_len = max(max_len, pos_map[m] - i)
if n not in pos_map:
pos_map[n] = i
return max_len
s = "4353526"
print(solve(s))입력
"4353526"
출력
5
시간 복잡도 분석
이 알고리즘은 문자열의 각 위치를 한 번씩 방문하고(O(n)), 각 위치에서 최대 10개의 비트 조합을 확인하므로 전체 시간 복잡도는 O(10 × n), 즉 O(n)입니다. 공간 복잡도 역시 마스크 값의 종류가 최대 2^10 = 1024개로 제한되므로 O(1)로 볼 수 있습니다. 덕분에 모든 부분 문자열을 일일이 검사하는 브루트포스 방식(O(n²) 이상)보다 훨씬 효율적으로 문제를 해결할 수 있습니다.