2021-01-04] Beautiful Arrangement

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3591/

Explore - LeetCode

알흠다운 배열... 문제 이해가 역시 쉽진 않은 바, 예시로 문제를 이해해보자.

 

<예시 1~2>

input N이 주어졌을때, 1~N까지의 배열에 대해 N개의 값을 가지는 순열을 만들고,

각 순열의 값이 i에 따라 나눠지면 그 순열은 알흠다운 배열이 된다.. 이 input N이 주어졌을 때, 만들어질

알흠다운 배열의 값을 구하는 것이다.

 

예시 1번처럼, N=2일때 1<=N<=15 라는 제약사항으로 배열 [1,2] 가 가질수 있는 순열은

원래 총 4개 : [1], [2], [1,2], [2,1] 여기서는 N개의 값을 가지는 순열이기 때문에 [1,2] , [2,1] 2개가 된다.

 

이후 처음 순열 [1,2] 부터 첫번째 값은 1로 나눠지고, 두번째 값 또한 1로 나눠지므로 [1,2]는 알흠다운 배열..

순열 [2,1]는 순열 첫번째 값 2가 1로 나눠지고, N 값 2가 순열 2번째 값 1로 나눠지므로 [2,1]도 알흠다운 배열

 

즉 N이 2일때, 알흠다운 배열은 2개가 된다. 이러한 조건을 가지는 총 개수를 구하는 것이 문제.

 

필자 또한 두가지의 예시로는 이해가 되지 않아, 마지막 예시로 N=3일때를 만들어보자.

 

N=3일때 필요한 순열 ( 총 6개 )

[1,2,3] , [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

 

1) [1,2,3]

  - i가 1일때, perm[1] = 1, 1/1==0 이 성립

  - i가 2일때, perm[2] = 2, 2/2==0 이 성립

  - i가 3일때, perm[3] = 3, 3/3==0 이 성립

    -> 알흠다운 배열

2) [1,3,2]

  - i가 1일때, perm[1] = 1, 1/1==0 이 성립

  - i가 2일때, perm[2] = 3, 3/2==0 이 실패, 2/3==0 또한 실패

  - i가 3일때, perm[3] = 2, 2/3==0 이 실패, 3/2==0 또한 실패

    -> 아무것도 아님

3) [2,1,3]

  - i가 1일때, perm[1] = 2, 2/1==0 이 성립

  - i가 2일때, perm[2] = 1, 2/1==0 이 성립

  - i가 3일때, perm[3] = 3, 3/3==0 이 성립

    -> 알흠다운 배열

4) [2,3,1]

  - i가 1일때, perm[1] = 2, 2/1==0 이 성립

  - i가 2일때, perm[2] = 3, 3/2==0 이 실패, 2/3==0 또한 실패

  - i가 3일때, perm[3] = 1, 3/1==0 이 성립

    -> 아무것도 아님

5) [3,1,2]

  - i가 1일때, perm[1] = 3, 3/1==0 이 성립

  - i가 2일때, perm[2] = 1, 2/1==0 이 성립

  - i가 3일때, perm[3] = 2, 3/2==0 이 실패, 2/3==0 또한 실패

    -> 아무것도 아님

6) [3,2,1]

  - i가 1일때, perm[1] = 3, 3/1==0 이 성립

  - i가 2일때, perm[2] = 2, 2/2==0 이 성립

  - i가 3일때, perm[3] = 1, 3/3==0 이 성립

    -> 알흠다운 배열

 

총 N이 3일때 알흠다운 배열의 개수는 3개이다.

 

자 이제 문제풀이를 해보자!! 

 

문제풀이 1차 실패) BF(Brute Force 기법) Time out or Memory leak

모든 순열에 대해서 생성하는  permutations를 쓰니.. 만드는데에만 해도 time out이 발생

이렇게 푸는 것은 아닌 것으로 보인다.. 좋은 알고리즘이 아니라는 것이 증명되는 부분.

( 시간이 많이 소요되지만 방법자체는 모두 다 검사하므로 낮은 N에서는 실패하진 않았음 )

 

from itertools import permutations

class Solution(object):
    def countArrangement(self, n):         
        """
        :type n: int
        :rtype: int
        """
        arr=[]
        cnt=0
        checked=0
        falseval=[]
        for i in range(1,n+1):
            arr.append(i) # 주어진 N에 대해서 1-N까지의 배열로 만든다.
            
        per=list(permutations(arr,n)) # 만든 List를 N에 대한 순열로 만들고 다시 list 화
        print(per)

        for idx in range(len(per)):
            perm=list(per[idx]) # 모든 순열에서 첫번째 순열값을 list화 ( 순열의 값이 tuple 형식이므로 )
            print(perm)
            falsecheck=False # 굳이 돌 필요 없을때를 위한 bool 값
            if falseval: # 밑에서 falseval에 값을 추가해준다면 if문 실행
                for fv in falseval:
                    if fv[0]==perm[fv[1]-1]: #검사할 순열의 falsevalue가 있다면 falsecheck update
                        falsecheck=True
                        break
            if falsecheck:
                continue 
            checked=0             
            for d in range(1,len(perm)+1): 한 순열에 대해 알흠다운 배열 검사 시작
                print("idx={},d={},perm[d-1]:{}".format(idx,d,perm[d-1]))
                if (perm[d-1]%d) == 0 or (d%perm[d-1])==0: # 알흠다운 배열일수 있는지 check!
                    print("checked!")
                    checked=checked+1
                else: # 알흠다운 배열이 아니면 이미 이 순열은 안대! 틀린놈이지!
                    falseval.append([perm[d-1],d]) # 3이 2번째 들어가있는 것과 같이 무조건 에러나는 value를 모아줌.
                    break
            if checked==n: # 검사가 끝나고 알흠다운배열에 대한 조건이 만족하면 checked의 값이 N과 동일해진다.
                cnt=cnt+1 # 그러면 cnt값 증가
        print(cnt)
             
        return cnt
        

 

문제풀이) 같이 풀고 있는 동기의 답으로 이해를 해보자.

 

class Solution:
    def countArrangement(self, n: int) -> int:
        def recursive(n, curr_arr, ret):
            #print(n, curr_arr, ret)
            cur_len = len(curr_arr)
            if cur_len == n+1:                
                if ret+1 == n:
                    return 1
                else:
                    return 0
            res = 0
            for i in range(1, n+1):
                #et = -1
                if i not in curr_arr and (i % cur_len == 0 or cur_len % i == 0):
                    tmp = curr_arr + [i]
                    res += recursive(n, tmp, ret+1)
            return res
        if n == 1:
            return 1
        ret = 0
        for i in range(1, n+1): #1st elem is always passed
            ret += recursive(n, [0,i],0)
            #print(ret)
        return ret

재귀적으로 순열 중 예시로 순서 2번째의 값이 3이 있으면 나눠지지 않으므로 무조건 완벽하지 않는 것을 이용하여,

최대한 for문을 적게도는 방법으로 N이 3일때 아래와 같이 배열과 값을 체크하며 순회하여 Time안에 성공한다..

( 다음번엔 더 좋은 코드를 고민해보자.. )

 

# 동기가 짠 코드의 N이 3일때의 print 출력내용

3 [0, 1] 0
3 [0, 1, 2] 1
3 [0, 1, 2, 3] 2
1
3 [0, 2] 0
3 [0, 2, 1] 1
3 [0, 2, 1, 3] 2
2
3 [0, 3] 0
3 [0, 3, 1] 1
3 [0, 3, 2] 1
3 [0, 3, 2, 1] 2