[코딩 테스트] 2026-04-03 — 순열

오늘의 문제 선정 이유

 

여러 서비스의 실행 순서를 모두 따져보는 경우가 많아, 백트래킹의 대표 유형인 순열을 오늘 주제로 골랐습니다.

문제 설명

당신은 여러 개의 독립적인 작업을 실행하는 자동화 도구를 만들고 있습니다.
각 작업은 한 번씩만 실행해야 하며, 실행 순서는 자유롭게 정할 수 있습니다.

중복이 없는 정수 배열 tasks가 주어질 때, 만들 수 있는 모든 실행 순서를 구하세요.

단, 결과는 다음 규칙을 따라야 합니다.

• 각 순서는 tasks의 원소를 정확히 한 번씩 사용해야 합니다.

 

• 같은 순서는 한 번만 포함해야 합니다.

 

• 반환 순서 자체는 자유롭습니다.

예를 들어 tasks = [2, 5, 7] 이면 가능한 실행 순서는 총 3! = 6개입니다.

입출력 예시

[text]입력: tasks = [1, 2, 3]
출력: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
설명: 3개의 작업을 한 번씩 모두 배치하는 모든 경우의 수는 6개입니다.

[text]입력: tasks = [4, 9]
출력: [[4,9],[9,4]]
설명: 2개의 작업이므로 가능한 순서는 2개입니다.

[text]입력: tasks = [8]
출력: [[8]]
설명: 작업이 1개뿐이면 가능한 순서는 자기 자신 하나뿐입니다.

제약 조건

• 1 <= tasks.length <= 8

 

• -10 <= tasks[i] <= 10

 

• tasks의 모든 원소는 서로 다릅니다.

 

• 시간 제한은 일반적인 코딩 테스트 환경을 가정합니다.

 

• 결과 개수는 최대 8! = 40320개입니다.

풀이 접근법

핵심 아이디어

이 문제는 현재까지 고른 원소 뒤에, 아직 사용하지 않은 원소를 하나씩 붙여 나가면 됩니다.
모든 순서를 빠짐없이 만들어야 하므로, 한 단계씩 선택하고 되돌아오는 backtracking이 가장 자연스럽습니다.
순열은 "자리를 하나 고정하고, 나머지 자리에 다시 같은 문제를 푸는 구조"라서 재귀와 잘 맞습니다.

단계별 풀이 과정

1. path 배열에 현재까지 선택한 순서를 저장합니다.
2. used 배열로 각 원소를 이미 사용했는지 기록합니다.
3. path의 길이가 tasks.length와 같아지면 완성된 순열이므로 결과에 복사해서 넣습니다.
4. 아직 사용하지 않은 원소를 하나 선택해 path에 추가합니다.
5. 재귀 호출로 다음 자리를 채웁니다.
6. 호출이 끝나면 마지막 선택을 되돌려 다음 경우를 탐색합니다.

코드 풀이

Python

 

[python]def solution(tasks):
    result = []
    used = [False] * len(tasks)
    path = []

    def dfs():
        # 모든 원소를 다 사용했다면 하나의 순열 완성
        if len(path) == len(tasks):
            result.append(path[:])
            return

        for i in range(len(tasks)):
            # 이미 사용한 원소는 건너뜀
            if used[i]:
                continue

            # 현재 원소 선택
            used[i] = True
            path.append(tasks[i])

            # 다음 자리 탐색
            dfs()

            # 선택 되돌리기
            path.pop()
            used[i] = False

    dfs()
    return result


# 실행 예시
if __name__ == "__main__":
    print(solution([1, 2, 3]))

JavaScript

 

[javascript]function solution(tasks) {
  const result = [];
  const used = new Array(tasks.length).fill(false);
  const path = [];

  function dfs() {
    // 모든 원소를 다 사용했다면 하나의 순열 완성
    if (path.length === tasks.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < tasks.length; i++) {
      // 이미 사용한 원소는 건너뜀
      if (used[i]) {
        continue;
      }

      // 현재 원소 선택
      used[i] = true;
      path.push(tasks[i]);

      // 다음 자리 탐색
      dfs();

      // 선택 되돌리기
      path.pop();
      used[i] = false;
    }
  }

  dfs();
  return result;
}

// 실행 예시
console.log(solution([1, 2, 3]));

시간·공간 복잡도

• 시간 복잡도: O(N × N!) — 순열 개수가 N!개이고, 각 결과를 저장할 때 길이 N만큼 복사합니다.

 

• 공간 복잡도: O(N × N!) — 최종 결과 저장 공간이 가장 크고, 재귀 호출 스택과 used, path는 O(N)입니다.

틀리기 쉬운 포인트

• result.append(path)처럼 현재 배열 자체를 넣으면, 이후 값이 바뀌어서 결과가 모두 같아질 수 있습니다. 복사본을 넣어야 합니다.

 

• 재귀가 끝난 뒤 path.pop()과 used[i] = False를 꼭 해줘야 합니다. 이 되돌리기를 빼먹으면 다음 경우를 만들 수 없습니다.

 

• 입력이 1개일 때도 정상 동작해야 합니다. 빈 결과가 아니라 [[x]]가 나와야 합니다.

유사 문제 패턴

• 조합 생성: 순서는 중요하지 않고, 일부 원소만 뽑는 문제입니다. 백트래킹 구조는 비슷하지만 탐색 방식이 다릅니다.

 

• 부분집합 생성: 각 원소를 넣을지 말지만 결정하는 문제입니다. 재귀 트리 구조를 익히기에 좋습니다.

 

• 제약이 있는 순열: 모든 순열이 아니라, 특정 조건을 만족하는 순서만 찾는 문제입니다. 예를 들어 인접한 두 값의 차이가 1이면 안 되는 경우가 있습니다.

---