소문자로 이루어진 문자열 s가 주어졌을 때, 문자열에 등장하는 각 알파벳의 빈도(출현 횟수)를 임의의 순서로 재배열했을 때 레카만 수열(Recaman's Sequence)의 첫 번째 항을 제외한 부분 수열과 일치하는지 확인하는 것이 이번 글의 목표입니다.
레카만 수열이란?
레카만 수열은 다음과 같은 점화식으로 정의되는 수열입니다.
an = 0 (n = 0일 때)
an = an-1 - n (an-1 - n이 양수이고 해당 값이 아직 수열에 없을 때)
an = an-1 + n (그 외의 경우)
즉, 이전 항에서 n을 뺀 값이 양수이면서 아직 수열에 등장하지 않았다면 값을 빼고, 그렇지 않으면 더하는 방식으로 수열이 만들어집니다.
레카만 수열의 일부 항은 다음과 같습니다.
[0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, ...]
첫 번째 항인 0은 무시하고, 나머지 항들만 비교 대상으로 삼습니다.
문제 예시
입력이 s = "pppuvuuqquuu"라고 가정해 보겠습니다. 각 문자의 빈도는 (p, 3), (u, 6), (v, 1), (q, 2)이며, 이 빈도 값들을 모으면 [1, 3, 6, 2]가 됩니다. 이는 레카만 수열의 처음 네 항 [1, 3, 6, 2]와 정확히 일치하므로 결과는 True입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- freq := 문자열 s의 모든 문자와 그 빈도를 저장하는 맵(딕셔너리)
- n := freq의 크기, 즉 고유한 문자의 개수
- array := 레카만 수열의 처음 n개 항
- f := 1 (모든 빈도가 일치함을 나타내는 플래그)
- freq의 각 문자에 대해 다음을 수행합니다.
- is_found := 0으로 초기화
- j를 1부터 n까지 반복하면서 freq[keys]와 array[j]가 같은지 확인하고, 같으면 is_found := 1로 설정한 뒤 내부 반복을 종료
- is_found가 거짓이면 f := 0으로 설정하고 전체 반복을 종료
- f가 1이면 True, 아니면 False를 반환
구현 예시
아래 파이썬 코드를 통해 실제 동작을 확인해 볼 수 있습니다.
from collections import defaultdict
def recaman(array, n) :
array[0] = 0
for i in range(1, n + 1):
temp = array[i - 1] - i
for j in range(i):
if array[j] == temp or temp < 0:
temp = array[i - 1] + i
break
array[i] = temp
def solve(s) :
freq = defaultdict(int)
for i in range(len(s)) :
freq[s[i]] += 1
n = len(freq)
array = [0] * (n + 1)
recaman(array, n)
f = 1
for keys in freq.keys() :
is_found = 0
for j in range(1, n + 1) :
if freq[keys] == array[j]:
is_found = 1
break
if not is_found:
f = 0
break
return True if f else False
s = "pppuvuuqquuu"
print(solve(s))
입력
"pppuvuuqquuu"
출력
True
시간 복잡도 분석
recaman 함수는 각 항을 계산할 때 이전 항들을 모두 검사해야 하므로 O(n²)의 시간이 걸립니다. solve 함수 역시 각 문자의 빈도를 수열의 항들과 하나씩 비교하므로 O(n²)이며, 따라서 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 수열 배열과 빈도 맵을 저장하는 데 필요한 O(n)입니다.