526. Beautiful Arrangement

526. Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/

문제

순열 중에서 해당 조건을 만족하는 순열 개수를 구하는 문제이다.
예를 들어 n=3일 때 나올 수 있는 순열은 다음과 같다.
(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)이다.
만족하는 순열은 (1,2,3) (2,1,3) (3,2,1)이고
만족하지 않는 순열은 (1,3,2) (2,3,1) (3,1,2) 이다. 그 이유는 3 나누기 2가 0으로 나누어 떨어지지 않기 때문이다. 즉 n=3일 땐 답은 3이 된다.

풀이

Recursion(재귀)로 순열 나타내기

다음과 같이 순열을 나타낼 수 있다. 문제는 타켓과 인덱스가 서로 나누어 떨어질 때에 순열을 구해야 하므로 다음과 같은 조건을 추가한다. 조건이 맞다면 재귀함수를 호출하면 될 것이고 조건이 틀리다면 재귀함수를 호출할 필요가 없을 것이다.

로직은 다음과 같다.
예를 들어 n = 3이라면 s = [1,2,3] 이 될 것이다.
for문을 통해 인덱스 별로 pop을 하면 i(인덱스) = 0일 때 target = 1이 될 것이고 arr = [2,3]이 될 것이다.
target에 대해서 조건 검사를 하고 맞다면 재귀함수를 호출한다. 그러면 다음 재귀함수에서는 arr = [2,3], cnt = 2인 상태에서 재귀함수를 실행한다.
그리고 cnt = n이면 해당 순열에 존재하는 원소들 모두 조건에 성립한다는 소리이므로 ans을 1증가 시킨다.

결과