순열

[hsskey]

문제 설명

순열 생성 문제: 주어진 문자열의 모든 가능한 순열을 생성하는 프로그램을 작성

📝 제약조건

• 입력 문자열 s의 각 문자는 중복되지 않는다.
• 출력은 모든 가능한 순열을 포함하는 배열이어야 한다.

💡 예시

• Input: "123"
• Output: ["123", "132", "213", "231", "312", "321"]

문제 해결 과정

Step 1: 문제 이해하기

작은 예시로 풀어보기:

Input: "12"
사람이 푸는 방법:
1. 첫 번째 자리에 1을 놓고, 나머지 2로 순열 만들기 -> "12"
2. 첫 번째 자리에 2를 놓고, 나머지 1로 순열 만들기 -> "21"

Step 2: 접근 방법

문제의 일반화 규칙 찾기:

1. 한 문자를 고정하고
2. 나머지 문자들로 가능한 모든 순열을 만든다
3. 이 과정을 모든 문자에 대해 반복한다

약식 알고리즘 표:

입력: s = "123"
1단계: "1"을 고정
  ↓
남은문자 "23"으로 순열만들기
  ↓
2단계: "2"를 고정
  ↓
남은문자 "3"으로 순열만들기
  ↓
결과 합치기: "1" + ("2" + "3")

Step 3: 코드 설계

모듈화:

/**
 * 입력: 문자열 s
 * 출력: 가능한 모든 순열의 배열
 * 예) 입력: "12" -> 출력: ["12", "21"]
 */
function permute(s) {
    // 구현
}

Step 4: 코드 구현

function permute(s) {
    if (s.length <= 1) {
        return [s];
    }
    let arr = [];
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        let remaining = s.slice(0, i) + s.slice(i + 1);
        // 재귀처리
        for (let perm of permute(remaining)) {
            // 데이터 통합
            arr.push(char + perm);
        }
    }
    return arr;
}

console.log(permute('12'));