Portfolio

📄문제

참고 자료

BOJ - 백트래킹 입문문제

✏️풀이

재영

일단 가장 직관적인 건 재귀함수임니다.

패턴을 봄니다. 이때 [1,2,3][1,3,2][2,1,3],[2,3,1],....을 보면, 결국 forEach를 통해 맨 앞을 순회하는 걸 알 수 이씀니다.

맨 앞을 놓되, 나머지들을 다시 재귀를 돌려 결과를 만들어봄니다. 그리고 result 때 이렇게 만들어진 결과들을 head와 합쳐 넣어줌니다. 그러면 결국 밑에서부터 [3] [2,3] [2] [3,2] [1,2,3] [1,3,2] 등이 만들어짐니다.

결과적으로 답이 나옴니다.


const permute = nums => {
	// 결과를 담는 변수
  const result = [];

	// 백트래킹 -> 만약 이제 하나밖에 남지 않았다면 배열로 리턴.
  if (nums.length === 1) return [nums];

	// nums array 값들을 `forEach`로 순회합니다. 이때 순회되는 값을 `head`라 합니다.
  nums.forEach((head, idx) => {
		// `head`를 제외한 나머지 값
    const tails = nums.filter((_, tailIdx) => tailIdx !== idx);
		// 그래서 결과적으로 재귀를 다시 실행합니다.
		// (그러면 이제 붙여야 할, 애들의 배열이 나오겠죠?! = 재귀로 나온 result)
    const permutedTails = permute(tails);
		
		// 재귀로 나온 result를 돌려서 
    permutedTails.forEach(permutedTail => {
			// 이제 head에 붙여줍니다.
      result.push([head, ...permutedTail]) 
    })
  })
	// 반환되는 결과는 다시 재귀를 호출했던 스코프로 돌아가서 `permutedTails`가 되거나, 
	// 결과 값을 반환하는 거죠!
  return result;
}
//96ms

효성


function permute(nums) {
    
    const permutes = [];
    
    function updatePermutes(pivot) {
        if(pivot === nums.length) {
           permutes.push([...nums]);
           return;
        }
        
        for(let i = pivot; i < nums.length; i++) {
            [nums[pivot], nums[i]] = [nums[i], nums[pivot]];
            updatePermutes(pivot+1);
            [nums[pivot], nums[i]] = [nums[i], nums[pivot]];
        }
    }
    
    updatePermutes(0);
    return permutes;
};

현석


var permute = function(nums) {
    const isSelected = new Array(nums.length).fill(false);
    const result = [];
    const permutation = [];
    
    const recursion = (count) => {
        
        if (count === nums.length ) {
            result.push([...permutation]);
            return
        }
        
        for (let i = 0; i < nums.length; i++) {
	          if (!isSelected[i]) {
						    isSelected[i] = true;
                permutation.push(nums[i]);
                recursion(count +1);
                permutation.pop();
                isSelected[i] = false	
						}
            
        }
        
    }
    recursion(0)
    return result;
};

태중

예전에 비슷한 문제를 풀어봤던 방법을 참조해서 풀었습니다.

checkArray를 통해 집합 내 숫자를 넣었는지 안넣었는지 확인하고,

tempArray라는 임시 집합을 만들어 answer에 push하는 방식으로 풀었습니다.


function permute(nums){         
    let answer=[];
    const n=nums.length;
    let checkArray=Array.from({length:n}, ()=>0);
    let tempArray=Array.from({length:n}, ()=>0);

    function DFS(L){
        if(L===n){
            answer.push(tempArray.slice()); // 깊은복사
        }
        else{
            for(let i=0; i<n; i++){
                if(checkArray[i]===0){
                    checkArray[i]=1;
                    tempArray[L]=nums[i];
                    DFS(L+1);
                    checkArray[i]=0;
                }
            }
        }
    }
    DFS(0);
    return answer;
}

Permutations

📄문제

참고 자료

✏️풀이