294. 반복되지 않는 단어

아현·2021년 9월 7일
0

Algorithm

목록 보기
308/400

백준




1. 재귀


아직 못 품


import sys
import collections
sys.setrecursionlimit(10 ** 6)
k, n, a = map(int, input().split())

#a는 알파벳 순으로 a번까지
#n은 전체 개수
alpha = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]

result = []
array = []

def check(array):
    dict = collections.Counter()
    window = 1
    while window <= n:
        for i in range(n - window + 1):
            dict[''.join(array[i:i + window])] += 1

        window += 1
        print(dict)
    
    if dict.most_common(1)[0][1] == k - 1:
        return True
    else:
        False

def make_array(cnt):
    global alpha, result
    if cnt == n:
        if check(array):
            result.append(''.join(array))
            return
        #print(array)
        return
        
    for a in alpha[:k]:
        array.append(a)
        make_array(cnt + 1)
        array.pop()

    
    
make_array(0)

#result.sort()

print(result)


  • 슬라이딩 윈도우로 매번 배열을 점검하여 가장 긴 반복이 k - 1인 것을 찾아내려고 했는데 아마 AA의 경우 A 단독에서 4로 계산되어 제외되어 버리는 것 같다.

  • 그 이유는 ABA가 연속해서 3번 반복되기 때문이다.

    • 이 부분이 조금 헷갈린다.
profile
For the sake of someone who studies computer science

0개의 댓글