[백준] 15651번 N과 M - 3 (C++, JAVA)

15651번: N과 M (3)

N개 중에 중복 포함, 순서를 고려하여 M개를 뽑는 중복 순열 문제이다.

순열과 다른 점은 중복을 체크해줄 필요 없기 때문에 check배열만 없애면 된다.

 

자바는 Scanner + print 써서 그냥 제출하니까 시간 초과 나길래

Scanner 대신 BufferedReader를 썼더니 또 시간 초과됐다 (자바 싫어)

찾아보니 print가 시간이 꽤 오래 걸린다 하더라

그래서 출력 부분을 StringBuilder로 넣어준 뒤 마지막에 한 번만 출력시켰더니 통과

 

< C++ 코드 >

#include <iostream>
#include <vector>
using namespace std;
vector <int> v;

int cnt = 0;
void multiPermutation(int N, int M) {
	if (cnt == M) {
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	}
	else {
		for (int i = 0; i < N; i++) {
			v.push_back(i + 1);
			cnt++;
			multipermutation(N, M);
			v.pop_back();
			cnt--;
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;

	multipermutation(N, M);

	return 0;
}

 

< JAVA 코드 >

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_15651_N과M_3 {
	private static int N, M;
	private static int arr[];
	private static StringBuilder sb = new StringBuilder();
	
	public static void permutation(int cnt) {
		if(cnt == M) {
			for(int val : arr) sb.append(val).append(' ');
			sb.append('\n');
			return;
		}
		
		for(int i = 0; i < N; i++) {
			arr[cnt] = i + 1;
			permutation(cnt + 1);
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); arr = new int[M];
		permutation(0);
		System.out.println(sb);
	}
}