[백준 C++] 15649 N과M endl

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

https://www.acmicpc.net/problem/15649

먼저 DFS로 순열을만들되, 중복이불가능함을 DFS안에 구현하면되는문제이다. 따라서 DFS로 노드를 방문할때 이미 찾은 원소인지를 확인하기위한 bool배열, 원소를 저장한 arr배열, 결과를 저장할 vector를 선언하면 된다.

해서 답을 제출했는데....
왜 시간초과가뜨지??

코드를 전부 수정하다보니 알게된사실이..
std::endl 함수는 '\n' 과 달리 버퍼를 flush하는 기능까지 겸비한 얘였다.
따라서 반복적으로 수행될시 비효율적인 코드가되는것.

추가로 std::flush라고 줄바꿈없이 버퍼의 내용을 출력만하는 함수또한있다.

앞으로 endl은 안써야겠군..

#include <bits/stdc++.h>
using namespace std;

int n, m, *arr;
bool* visited;
vector<int> seq;

void DFS(int num) {
	if (num == m) { //원하는 깊이(m)까지 탐색한경우
		for (int i = 0; i < m; i++) 
			cout << seq[i] << " "; //탐색 결과출력
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (visited[i]) //중복을 제외하므로 방문시 실행안함
			continue;
		visited[i] = true; //중복을 제외하므로 방문함을 기록
		seq.push_back(arr[i]);
		DFS(num + 1); //DFS핵심 부분 (현재방향대로 깊숙히 탐색(
		seq.pop_back(); //다음 탐색을 위한 초기화
		visited[i] = false; //초기화
	}
}

int main(void) {
	cin >> n >> m;
	visited = new bool[n];
	arr = new int[n];
	for (int i = 0; i < n; i++) {
		arr[i] = i + 1;
		visited[i] = false;
	}
	DFS(0);

	return 0;
}