💻 백준 15663: N과 M (9)

문제 소개 🧐

N개의 자연수가 주어졌을 때, 이 중에서 M개를 골라 만들 수 있는 모든 수열을 구하는 문제다. 단, 몇 가지 조건이 있다.

  • 주어진 N개의 자연수를 사용해야 한다.
  • 수열의 길이는 M이어야 한다.
  • 중복되는 수열은 한 번만 출력해야 한다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입력 📝

  • 첫째 줄: N과 M (1 ≤ M ≤ N ≤ 8)
  • 둘째 줄: N개의 자연수 (10,000 이하)

출력 📤

  • 조건을 만족하는 수열을 한 줄에 하나씩, 공백으로 구분하여 출력한다.

제한 ❌

  • 시간: 1초
  • 메모리: 512MB

나의 풀이: itertools.permutations 활용 👊

Idea

N과 M 시리즈의 아홉 번째 문제! 이번 문제의 핵심은 주어진 숫자들로 순열을 만들되, 결과적으로 중복되는 수열은 제거하는 것이다.

  1. itertools.permutations를 사용하면 주어진 숫자들로 길이가 M인 모든 순열을 손쉽게 만들 수 있다.
  2. 생성된 순열들을 정렬하여 사전 순으로 만든다.
  3. 출력하기 전에, 바로 이전에 출력했던 수열과 현재 수열이 같은지 비교한다. 만약 같다면 중복이므로 건너뛰고, 다를 때만 출력한다.

이 간단한 아이디어로 중복 출력을 효과적으로 막을 수 있다.

Code

import sys
from itertools import permutations

# 입력 처리
n, m = map(int, sys.stdin.readline().split())
num_li = list(map(int, sys.stdin.readline().split()))

# 1. 주어진 숫자로 길이가 m인 모든 순열을 구하고 정렬한다.
perm_li = sorted(list(permutations(num_li, m)))

# 2. 중복을 제거하며 출력한다.
prev_perm = ()
for p in perm_li:
    if p != prev_perm:
        print(*p)
    prev_perm = p

Result

  • 성공! ✅
  • itertools 라이브러리의 강력함을 다시 한번 느낄 수 있었다. 순열을 직접 구현하는 것보다 훨씬 간결하고 효율적으로 문제를 해결할 수 있었다. 중복 제거 로직도 간단하게 처리하여 성공!

개선할 부분 🤔

  • 백트래킹 직접 구현: itertools를 사용하지 않고 백트래킹으로 순열을 직접 생성하는 방법도 있다. 이 경우, 방문 여부를 체크하는 visited 배열과 함께, 같은 레벨에서 동일한 숫자를 다시 사용하지 않도록 체크하는 로직을 추가하면 더 효율적인 중복 제거가 가능하다. 하지만 itertools가 워낙 강력해서 이 문제에서는 큰 차이가 없을 수도 있다.
  • 메모리 효율: 만약 N이 매우 크다면 모든 순열을 리스트에 저장하는 것이 메모리 부담이 될 수 있다. 그럴 땐 생성과 동시에 출력 및 중복 체크를 하는 방식이 더 유리할 것이다.