비어 있지 않은 문자열 str 과 정수 k 가 주어지면 동일한 문자가 서로 최소한 거리 k가 되도록 문자열을 재정렬합니다.
모든 입력 문자열은 소문자로 제공됩니다. 문자열을 재배열할 수 없는 경우 빈 문자열 ""을 반환합니다.
예시 1:
str = “tutorialspoint”, k = 3 Answer: “tiotiotalnprsu”
같은 문자는 3자 이상 떨어져 있습니다.
str = "aabbcc", k = 3 Answer: "abcabc" The same characters are at least 3 character distance apart.
예시 2
str = "aaabc", k = 3 Answer: "" It is not possible to rearrange the string.
예시 3:
str = "aaadbbcc", k = 2 Answer: "abacabcd" Another possible answer is: "abcabcda" The same characters are at least 2 character distance apart.
예시
MAX = 128
# A structure to store a character 'char' and its frequency 'freq'
# in input string
class charFreq(object):
def __init__(self,char,freq):
self.c = char
self.f = freq
# A utility function to swap two charFreq items.
def swap(x, y):
return y, x
# A utility function
def toList(string):
t = []
for x in string:
t.append(x)
return t
# A utility function
def toString(l):
return ''.join(l)
# A utility function to maxheapify the node freq[i] of a heap stored in freq[]
def maxHeapify(freq, i, heap_size):
l = i*2 + 1
r = i*2 + 2
largest = i
if l < heap_size and freq[l].f > freq[i].f:
largest = l
if r < heap_size and freq[r].f > freq[largest].f:
largest = r
if largest != i:
freq[i], freq[largest] = swap(freq[i], freq[largest])
maxHeapify(freq, largest, heap_size)
# A utility function to convert the array freq[] to a max heap
def buildHeap(freq, n):
i = (n - 1)//2
while i >= 0:
maxHeapify(freq, i, n)
i-=1
# A utility function to remove the max item or root from max heap
def extractMax(freq, heap_size):
root = freq[0]
if heap_size > 1:
freq[0] = freq[heap_size-1]
maxHeapify(freq, 0, heap_size-1)
return root
# The main function that rearranges input string 'str' such that
# two same characters become d distance away
def rearrange(string, d):
# Find length of input string
n = len(string)
# Create an array to store all characters and their
# frequencies in str[]
freq = []
for x in range(MAX):
freq.append(charFreq(0,0))
m = 0
# Traverse the input string and store frequencies of all
# characters in freq[] array.
for i in range(n):
x = ord(string[i])
# If this character has occurred first time, increment m
if freq[x].c == 0:
freq[x].c = chr(x)
m+=1
freq[x].f+=1
string[i] = '\0'
# Build a max heap of all characters
buildHeap(freq, MAX)
# Now one by one extract all distinct characters from max heap
# and put them back in str[] with the d distance constraint
for i in range(m):
x = extractMax(freq, MAX-i)
# Find the first available position in str[]
p = i
while string[p] != '\0':
p+=1
# Fill x.c at p, p+d, p+2d, .. p+(f-1)d
for k in range(x.f):
# If the index goes beyond size, then string cannot
# be rearranged.
if p + d*k >= n:
print ("It is not possible to rearrange the string.")
return
string[p + d*k] = x.c
return toString(string)
string = "tutorialspoint"
print (rearrange(toList(string), 3) )
결과
tiotiotalnprsu