BAEKJOON 15649:N과 M(1)

 

제한시간 내 순열 만들기

15649번: N과 M (1)

---

코드

 

순열 자체를 구하는 속도는 빠르지만, 이를 하나씩 출력하는 과정에서 속도를 잡아먹는 것이 많기 때문에 stringstream에 출력할 문자열을 저장한 뒤, 최종에 한번 출력하도록 하여 속도 향상을 꾀함

#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

int visited[9];
int permutationList[9];
stringstream ss;

void bt(int maxValue, int depth, int maxDepth) {
	if (depth == maxDepth) {
		string str;
		for (int i = 0; i < maxDepth; ++i) {
			ss << permutationList[i] << " ";
		}
		ss << endl;
		return;
	}

	for (int i = 1; i <= maxValue; ++i) {
		if (!visited[i]) {
			visited[i] = true;
			permutationList[depth] = i;
			bt(maxValue, depth + 1, maxDepth);
			visited[i] = false;
		}
	}

}

int main() {

	int n, m;
	cin >> n >> m;
	bt(n, 0, m);
	cout << ss.str();
	return 0;
}

위 코드로 작성시 16ms로 나오고

ios.sync_with_stdio(0);
cin.tie(0);

위 두 함수를 사용하여 입출력 비동기화를 진행한 경우보다 빨랐음을 확인했다.

알고리즘 최적화도 최적화지만 큰 출력이 필요한 경우엔 여러번에 나눠 출력하는 것보다 모아서 한번에 출력하는게 속도 향상에 도움이 되었다.

 

뭣보다, 개인적으로 저 두 코드 사용하는게 꼼수같은 느낌이라 그리 선호하지도 않는다. 특히나 알고리즘을 공부하는 문제에 있어서, 저 명령을 통해서라야 통과할 수 있는 기준을 제시한 문제가 있다면 수정되어야하지 않을까.. 싶기도 하다.