[백준 15654번] N과 M (5) (C++ / Python)

 

permutation을 만들 때, 섞어야하는 배열이 있다면, 그 배열의 index를 섞는다 라고 생각하면 편하다.

하나를 여러번 뽑을 순 없으므로 visited[] bool 배열로 한 index가 두번 선택되게 하지 않게끔 막는다.

출력 조건이 사전순으로 증가하는(오름차순) 순서로 출력해야 하기 때문에 permutation을 실행하기 전에 sort후 실행한다.

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<int> v;
vector<int> permu;
bool visited[9];
int M, N;

void print_permu()
{
	for (int i = 0; i < permu.size(); i++)
	{
		cout << permu[i] << " ";
	}
	cout << '\n';
}
void dfs(int start)
{
	if ((int)permu.size() == M) {
		print_permu();
		return;
	}

	for (int i = 0; i < N; i++)
	{
		if (!visited[i]) {
			visited[i] = true;
			permu.push_back(v[i]);
			dfs(i + 1);
			permu.pop_back();
			visited[i] = false;
		}
		
	}


}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		int temp;
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	dfs(0);
}

 

Python 풀이

itertools에 permutation이 존재하니 사용하자.

import sys
from itertools import permutations
input = sys.stdin.readline

N, M = map(int,input().rstrip().split())
permu = list(map(int,input().rstrip().split()))

permu.sort()
permu_list = list(permutations(permu, M))
for item in permu_list:
    for i in item:
        print(i, end = ' ')
    print()