JS) 스왑 swap 순열 재귀함수, 경우의 수 구하는 함수 (두 숫자, 배열, 문자열 순서 바꾸기)

스왑 기본 동작

좌항에서 배열의 각 위치에 우항의 값을 차례대로 할당하는 방식

[a, b] = [b, a];​

• 우항: [b, a] → 우항에서 b와 a의 값이 평가.
• 좌항: [a, b] →  좌항에서 a와 b는 우항의 값을 차례대로 받는 것

결과적으로,  좌항의  a에는 b의 값이 들어가고  b에는 a의 값이 들어감.

 

 

 

 

순열 재귀함수 - 스왑

순열 (Permutation) 은 순서를 고려하여 나열하는 경우의 수

let input = ['a', 'b', 'c'];
let count = 0;
// 순열 재귀함수 (배열, 시작할위치, 순열길이)
const permutation = (arr, s, r) => {
  // 1. 재귀함수를 멈춰야할 조건
  if (s === r) {
    count++;
    console.log("arr.join(' '): ", arr.join(" "));
    return;
  }

  // 2. 재귀를 돌면서 변경되어야 될 부분 - 메인로직
  for (let i = s; i < arr.length; i++) {
     [arr[s], arr[i]] = [arr[i], arr[s]];  // 스왑-swap
    /*   
     *   우항: [arr[i], arr[s]] → ['b', 'a'] 의 값이
     *   좌항: arr[s] = 'b', arr[i] = 'a' 로 들어감. 그렇게 교환됨.
     */
    
    permutation(arr, s + 1, r); // 재귀호출 / 첫번째 선택했으니 s+1로 두번째 선택
    [arr[s], arr[i]] = [arr[i], arr[s]]; // 스왑을 원상복구 (백트래킹)
  }
};
permutation(input, 0, 2);
console.log('permutation_count: ', count);

//print
arr.join(' '):  a b c
arr.join(' '):  a c b
arr.join(' '):  b a c
arr.join(' '):  b c a
arr.join(' '):  c b a
arr.join(' '):  c a b
permutation1_count:  6

 

 

 

 

예제 1 두 숫자의 스왑

let a = 5; 
let b = 10; 

// 스왑 
[a, b] = [b, a]; 

console.log(a); // 10 
console.log(b); // 5

설명

1. 우항: [b, a] → [10, 5]
2. 좌항: [a, b] → a = 10, b = 5

이렇게 두 변수의 값을 교환.

 

---

예제 2 배열에서 두 값의 스왑

let arr = [1, 2, 3, 4]; 

// 스왑 
[arr[0], arr[3]] = [arr[3], arr[0]]; 

console.log(arr); // [4, 2, 3, 1]

설명

1. 우항: [arr[3], arr[0]] → [4, 1]
2. 좌항: arr[0] = 4, arr[3] = 1

배열의 첫 번째와 마지막 요소를 스왑하여 배열이 [4, 2, 3, 1]

 

---

예제 3 배열에서 두 값의 스왑 (중간값들 바꿀 때)

let arr = ['a', 'b', 'c', 'd']; 

// 스왑 
[arr[1], arr[2]] = [arr[2], arr[1]]; 

console.log(arr); // ['a', 'c', 'b', 'd']

설명

1. 우항: [arr[2], arr[1]] → ['c', 'b']
2. 좌항: arr[1] = 'c', arr[2] = 'b'

배열에서 인덱스 1과 2의 값 'b'와 'c'를 스왑하여 배열은 ['a', 'c', 'b', 'd']

 

---

예제 4 2차원 배열에서 값 스왑

let arr2D = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; 

// 2차원 배열에서 (0, 1)과 (1, 0)의 값 스왑 
[arr2D[0][1], arr2D[1][0]] = [arr2D[1][0], arr2D[0][1]]; 

console.log(arr2D); 
// 출력: [ 
// [1, 4, 3], 
// [2, 5, 6], 
// [7, 8, 9] 
// ]

설명

1. 우항: [arr2D[1][0], arr2D[0][1]] → [4, 2]
2. 좌항: arr2D[0][1] = 4, arr2D[1][0] = 2

2차원 배열에서 arr2D[0][1] (값 2)과 arr2D[1][0] (값 4)를 스왑하여 배열은 위와 같이 변경.

 

---

예제 5 문자열에서 문자 순서 바꾸기 

let str = 'hello'; 

// 문자열을 배열로 변환 후 스왑 
let arrStr = str.split(''); 
[arrStr[0], arrStr[4]] = [arrStr[4], arrStr[0]]; 

console.log(arrStr.join('')); // 'oellh'

설명

1. 우항: [arrStr[4], arrStr[0]] → ['o', 'h']
2. 좌항: arrStr[0] = 'o', arrStr[4] = 'h'

문자열을 배열로 변환하여 첫 번째와 마지막 문자를 스왑한 뒤, 다시 문자열로 결합하여 'oellh'로 바뀜.

알고리즘 문자열 뒤집기 문제에 많이 나옴. reverse()를 더 많이 씀.

 

 

 

경우의 수

재귀 사용 - 입력 값이 크면 스택 오버플로우가 발생할 수 있음.

// 경우의수 구하는 함수
const factorial = (n) => {
 if (n === 0 || n === 1) return 1; // 기본 조건 (종료 조건)
  return n * factorial(n - 1); // 재귀 호출
};
console.log(factorial(5)); // 120

const permutation = (n, r) => {
  return factorial(n) / factorial(n - r);
};

console.log("permutation_경우의 수 중 순서를 고려한 순열 :" ,permutation(5, 3)); // 60

 

 

for문

const factorial = (n) => {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
};

console.log(factorial(5)); // 120

 

 

팩토리얼을 활용해 순열 구현

팩토리얼  P(n,r)=(n−r)!n!

0! = 1  / ​1! = 1  / 2! = 2  /  3!= 6  / 4! = 24  / 5! = 120  / 6! = 720  / 7! = 5,040  /  8! =  40,320  / 9! =  362,880

(영팩토리얼) !를 팩토리얼이라고 읽는다. 5!는 5팩토리얼. 5 부터 1까지 곱한다는 뜻.

 

const factorial = (n) => {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
};

const permutation = (n, r) => {
  return factorial(n) / factorial(n - r);
};

console.log(permutation(5, 3)); // 60

 

 

 

 

 

 

 

 

 

 

참고 

정승제쌤 유투브 팩토리얼 - https://www.youtube.com/watch?v=ByAh6UwtK1A