[BaekJoon] 백준 15663번 : N과 M (9)

15663번 : N과 M (9)

다른 N과 M 문제에 비해 해결방법을 찾기 어려웠던 문제였다..

내가 생각한 해결 방법은 주어진 자연수 중 중복 값을 찾아 따로 저장을 한다.

그리고 주어진 자연수 배열을 set 으로 바꾸어 중복 값을 없애고 이 set 으로 순열을 만든다.

4 3

2 4 4 9 이렇게 배열이 주어진 경우 중복 값 4 를 따로 저장한 뒤 2 4 9 배열로 만들고 순열을 만드는 것 이다.

그렇게 되면 이런 경우가 생기는데 노란색 형광칠이 된 경우가 가능한 경우이다.

답이 아닌 경우는 두 가지 경우가 있다.

첫 번째로 2 2 같이 중복 값이 아닌데 또 append 를 하는 경우 바로 continue 를 한다.

두 번째로 4 4 4 같이 4 4 는 가능하지만 또 4 가 들어오면 안되는 경우이다.

이 경우를 Counter 를 이용 해 찾아주었다.

처음 주어진 중복 값의 개수보다 스택에 있는 중복 값의 개수가 더 많아지면 바로 continue 를 한다.

예를들어 처음 주어진 배열에서 중복 값 4 는 두 개였는데 스택이 4 4 인 경우 4 를 또 넣어주면 중복 값의 개수가 세 개가 된다.

이렇게 두 가지 경우를 제외시켜주면 답을 구할 수 있다.

물론 Permutation 과 set 을 이용하면 코드 한 줄로 해결이 가능하다..

---

import sys
from collections import Counter


def DFS():
	if len(stack) == m:
		print(*stack)
		return

	for i in range(len(data)):
		if stack and data[i] in stack and data[i] not in duplicate:
			continue
		if data[i] in duplicate and count[data[i]] < Counter(stack)[data[i]] + 1:
			continue
		stack.append(data[i])
		DFS()
		stack.pop()


n, m = map(int, sys.stdin.readline().rsplit())
data = list(map(int, sys.stdin.readline().rsplit()))
count = Counter(data)
stack = []
duplicate = []

for key, value in zip(count.keys(), count.values()):
	if value > 1:
		duplicate.append(key)
data = sorted(list(set(data)))

DFS()

---

import sys
from itertools import permutations


n, m = map(int, sys.stdin.readline().rsplit())
data = map(int, sys.stdin.readline().rsplit())

for val in sorted(list(set(permutations(data, m)))):
	print(*val)