백준: 15663 N과 M (9)

N과 M 시리즈

• 원소가 1에서 N인 경우
  • 15649 N과 M (1)
  • 15650 N과 M (2)
  • 15651 N과 M (3)
  • 15652 N과 M (4)

• 원소가 주어지는 경우
  • N과 M (5 ~ 8)
  • N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다.

• 중복 원소가 존재하는 경우
  • 15663 N과 M (9)
  • N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다.

 

문제

15663번: N과 M (9)

 

문제 풀이

 N과 M (1 - 8)의 문제들은 원소가 중복되지는 않았다. 하지만 9 - 12번 문제는 원소가 중복되며 각 요건에 맞게 순열, 조합을 구하여야 한다. 해당 문제는 중복되는 원소가 있을 때, 순열을 구하는 문제로 set을 활용하면 쉽게 해결할 수 있다.

 

코드

DFS를 활용한 문제 풀이

from sys import stdin


def dfs(depth):
    global answer

    if depth == m:
        answer.add(tuple(nums[i] for i in check))
        return
    else:
        for i in range(n):
            if i in check:
                continue
            check[depth] = i
            dfs(depth + 1)
            check[depth] = -1


if __name__ == "__main__":
    # 중복된 순열을 추가하지 않도록 set으로 선언
    answer = set()
    n, m = map(int, stdin.readline().split())
    nums = sorted(list(map(int, stdin.readline().split())))
    # index 값을 저장하므로 -1로 초기화
    check = [-1] * m
    dfs(0)

    for num in sorted(list(answer)):
        print(*num)

 앞서 푼 문제와 다른 점이 있다면, 찾은 순열을 저장하는 answer를 set으로 선언하여, 중복된 값을 담지 않았다. 여기서 말하는 중복된 값은 (1, 7) (7, 1)과 같은 값이 아닌, (1, 7), (1, 7)을 의미하는 것이다.

 

itertools permutations를 활용한 풀이

from itertools import permutations

N, M = map(int, input().split())
nums = map(int, input().split())

for cases in sorted(list(set(permutations(nums, M)))):
    for case in cases:
        print(case, end=' ')
    print()