[Python] 백준15663 N과 M (9)

17 May 2023 in Study on Algorithm

백준15663 N과 M (9) 링크

문제

예제 입력

---

코드

import sys
from itertools import permutations

n, m = map(int, input().split())
arr = [x for x in map(int, sys.stdin.readline().split()) ]
res = sorted(set(permutations(arr, m)))

for lst in res:
    for num in lst:
        print(num, end=' ')
    print()

설명

파이썬을 통해서 사용자로부터 입력받아 순열과 중복 제거를 위해 set을 사용하여 N과 M (9)를 구현했습니다.

---

정리

import sys

n, m = map(int, input().split())
arr = [x for x in map(int, sys.stdin.readline().split()) ]
arr.sort()

lst = []
prev = 0    # flag - 중복 체크값 제어
visited = [0 for _ in range(n)]

# 인덱스 번호로 확인하면서 같은 자리에 같은 값은 prev로 제어
def backt(st):
    prev = 0
    if st == m:
        print(*lst)     # ' '.join(map(str, lst))
        return
    for i in range(n):
        if arr[i] != prev and visited[i] == 0:
            prev = arr[i]
            lst.append(arr[i])
            visited[i] = 1
            backt(st + 1)
            lst.pop()
            visited[i] = 0

backt(0)

그 외에도 백트래킹알고리즘을 사용하여 해결할 수 있습니다.

---

결과