Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 같은 문자가 최소 d 거리 이상 떨어지도록 문자열 재정렬하기

문제 개요

빈 문자열이 아닌 문자열 str과 정수 k가 주어졌을 때, 동일한 문자들이 서로 최소 k 거리 이상 떨어지도록 문자열을 재정렬하는 것이 목표입니다.

모든 입력 문자열은 소문자로만 구성되어 있으며, 주어진 조건에 맞게 재정렬하는 것이 불가능한 경우에는 빈 문자열("")을 반환해야 합니다.

예제

예제 1

str = "tutorialspoint", k = 3

결과: "tiotiotalnprsu"

동일한 문자들이 최소 3칸의 거리를 두고 배치되어 있는 것을 확인할 수 있습니다.

예제 2

str = "aabbcc", k = 3

결과: "abcabc"

같은 문자 'a', 'b', 'c'가 서로 3칸씩 떨어져 있습니다.

예제 3

str = "aaabc", k = 3

결과: ""

'a'가 세 번 등장하지만 문자열 길이가 5에 불과해 3칸 간격을 유지할 수 없으므로 재정렬이 불가능합니다.

예제 4

str = "aaadbbcc", k = 2

결과: "abacabcd"

"abcabcda" 역시 가능한 답 중 하나입니다. 동일한 문자들이 최소 2칸의 거리를 유지하며 배치되어 있습니다.

알고리즘 접근 방식

이 문제는 그리디(Greedy) 알고리즘과 최대 힙(Max Heap)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 입력 문자열을 한 번 순회하면서 각 문자의 빈도수를 계산합니다.
  2. 빈도수를 기준으로 최대 힙을 구성합니다.
  3. 힙에서 빈도가 가장 높은 문자를 하나씩 꺼내, 사용 가능한 첫 번째 위치부터 시작해 p, p+d, p+2d, ... 형태로 d 간격을 유지하며 배치합니다.
  4. 배치 과정에서 인덱스가 문자열 길이를 초과하면 조건을 만족하는 재정렬이 불가능하므로 종료합니다.

빈도가 높은 문자를 먼저 넓은 간격으로 배치해 두면, 나머지 문자들을 자연스럽게 빈 자리에 채워 넣을 수 있기 때문에 그리디 방식이 잘 작동합니다.

구현 코드

MAX = 128

# 문자와 해당 문자의 빈도수를 저장하기 위한 클래스
class charFreq(object):
    def __init__(self, char, freq):
        self.c = char
        self.f = freq

# 두 charFreq 객체를 교환하는 유틸리티 함수
def swap(x, y):
    return y, x

# 문자열을 리스트로 변환하는 유틸리티 함수
def toList(string):
    t = []
    for x in string:
        t.append(x)
    return t

# 리스트를 문자열로 변환하는 유틸리티 함수
def toString(l):
    return ''.join(l)

# 힙의 노드 freq[i]를 대상으로 최대 힙 속성을 유지하는 함수
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)

# 배열 freq[]를 최대 힙으로 변환하는 함수
def buildHeap(freq, n):
    i = (n - 1)//2
    while i >= 0:
        maxHeapify(freq, i, n)
        i -= 1

# 최대 힙에서 최댓값(루트)을 제거하고 반환하는 함수
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

# 입력 문자열을 재정렬하여 동일한 문자가 d 거리 이상 떨어지도록 하는 메인 함수
def rearrange(string, d):
    # 입력 문자열의 길이
    n = len(string)

    # 모든 문자와 빈도수를 저장할 배열 생성
    freq = []
    for x in range(MAX):
        freq.append(charFreq(0, 0))

    m = 0

    # 입력 문자열을 순회하며 각 문자의 빈도수를 freq[] 배열에 저장
    for i in range(n):
        x = ord(string[i])

        # 처음 등장한 문자라면 고유 문자 수 m을 1 증가
        if freq[x].c == 0:
            freq[x].c = chr(x)
            m += 1

        freq[x].f += 1
        string[i] = '\0'

    # 모든 문자로 최대 힙 구성
    buildHeap(freq, MAX)

    # 최대 힙에서 고유 문자를 하나씩 추출하여
    # d 거리 제약 조건에 맞게 str[]에 다시 배치
    for i in range(m):
        x = extractMax(freq, MAX-i)

        # str[]에서 비어 있는 첫 번째 위치 탐색
        p = i
        while string[p] != '\0':
            p += 1

        # x.c를 p, p+d, p+2d, ... , p+(f-1)d 위치에 채워 넣음
        for k in range(x.f):

            # 인덱스가 문자열 크기를 초과하면 재정렬 불가능
            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