💻 백준 15666번: N과 M(12)

문제 소개 🧐

N개의 자연수 중에서 M개를 고르는 모든 수열을 구하는 문제다. 단, 같은 수를 여러 번 골라도 되며, 수열은 비내림차순이어야 하고, 중복되는 수열은 출력하면 안 된다.

입력 📝

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

출력 📤

  • 조건을 만족하는 수열을 한 줄에 하나씩 출력한다.
  • 각 수열은 공백으로 구분하며, 사전 순으로 증가하는 순서로 출력해야 한다.

제한 ❌

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

첫 번째 시도: itertools와 Counter 활용 🚀

Idea

itertools.combinations_with_replacement를 사용하면 중복 조합을 쉽게 구할 수 있다.

  1. 정렬 및 중복 제거: 먼저 입력받은 숫자(nums)를 정렬한다. 그 후 collections.Counter를 사용해 입력값의 중복을 제거한 고유한 숫자 리스트를 만든다.
  2. 중복 조합 생성: 이 고유 숫자 리스트를 combinations_with_replacement에 넘겨 M개를 뽑는 모든 중복 조합을 생성한다.
  3. 중복 수열 제거 및 출력: combinations_with_replacement가 생성한 결과 리스트에는 중복된 조합이 있을 수 있다. 따라서 prev 변수를 두어 직전에 출력한 조합과 현재 조합을 비교하여, 같은 경우엔 출력하지 않고 넘어가는 방식으로 중복 출력을 방지했다.

Code

import sys
from itertools import combinations_with_replacement
from collections import Counter

n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()
# Counter를 사용해 고유한 숫자 리스트를 추출
nest_rm_nums_li = list(Counter(nums).keys())

com_li = list(combinations_with_replacement(nest_rm_nums_li, m))
prev = None

for com in com_li:
    # 직전 조합과 비교하여 중복 출력 방지
    if com == prev:
        continue
    prev = com
    print(*com)

Result

  • 결과: 정답! ✅
  • Counter로 입력의 중복을 제거하고, 출력 단계에서 prev 변수로 조합의 중복을 한 번 더 걸러내어 문제를 해결했다.

개선할 부분 🤔

  • itertools 라이브러리는 순열/조합 문제에서 매우 강력하다. 적극적으로 활용하자.
  • Counter를 사용해 고유 원소를 추출하는 방법도 유용하지만, 이 경우에는 sorted(list(set(nums)))가 더 간결한 코드가 될 수 있었다.

itertools와 Counter를 조합하여 문제를 해결했다. 출력 시 중복을 제거하는 로직을 추가한 것이 핵심이었다.