Beautiful Arrangement (Fail)

반응형

문제링크 : leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3591/

Explore - LeetCode

어제 노느라 못풀고 January LeetCoding Challenge 2021 3일차를 도전했다. 결과는 무참히 타임아웃으로 탈락.

숫자 n이 주어지면 1,2,3,4,5... 의 순차적인 배열과 그 배열의 순열들을 만든다. 이 때 이 배열의 모든 아이템이

• index로 값이 나뉘어지거나
• 값이 index로 나뉘어지면

beautiful arrangement라고 한다. 그리고 모든 순열을 검사하여 총 개수가 몇 개인지 return한다.

class Solution:
    def countArrangement(self, n: int) -> int:
        init = tuple(range(1,n+1))
        from itertools import permutations
        result = 0
        for items in permutations(init, n):
            beutiful = True
            for i, item in enumerate(items):
                if item % (i + 1) != 0 and (i + 1) % item != 0:
                    beutiful = False
                    break
            if beutiful:
                result += 1
        return result

n이 11개에서 타임아웃이 발생했다. 시험중인 문제라 해답도 없다. 너무 쉽게 접근한게 아닐까 생각된다. 문제를 푸는 것과 아득히 먼 옛날 본 알고리즘 책을 함께 보면서 감을 찾아야겠다. 그리고 이런거 풀 때 itertools 써서 순열을 구해도 되는건지 모르겠다. 일단, 오늘과 내일은 순열과 조합을 복습해야겠다.

저작자표시비영리동일조건