💻 백준 15654: N과 M(5)

문제 소개 🧐

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

  • N개의 자연수 중에서 M개를 고른 수열

입력 📝

  • 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
  • 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력 📤

  • 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

제한 ❌

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

첫 번째 시도: itertools.permutations ✅

Idea

itertools 라이브러리의 permutations 함수를 사용하면 주어진 리스트에서 M개의 원소를 뽑아 나열하는 모든 경우의 수(순열)를 쉽게 구할 수 있다. 문제에서 요구하는 것이 정확히 순열이므로, 이 함수를 활용하면 쉽게 해결할 수 있다. 입력받은 숫자들을 정렬한 후 순열을 구하면 사전 순으로 출력된다.

Code

import sys
from itertools import permutations

n, m = map(int, sys.stdin.readline().split())
nums = sorted(list(map(int, sys.stdin.readline().split())))

li = permutations(nums, m)

for l in li:
    print(*l)

Result

  • 성공! permutations를 사용하여 간단하게 해결했다. 입력받은 수를 정렬해줌으로써 사전순 출력 조건도 만족시킬 수 있었다.

개선할 부분 🤔

  • 이 문제 역시 itertools 없이 백트래킹으로 직접 순열을 구현하는 연습을 해보면 좋을 것 같다.