글 읽기 - C++ next_permutation 사용했습니다(메모리초과가 납니다)

dyl9912 2년 전 0

모음 순열 따로, 자음 순열 따로 해서,

선택된 모음 순열에 따라 자음 순열을 정해서 ans에 push하는 식으로 구성했습니다.

vector<string> ans에 다 쌓아 놓는 부분이 문제일까요?

sort도 자주 하는데 많이 비효율적인 코드로 보시나요?

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

bool isvowel(char c) {
	if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
		return true;
	return false;
}

vector<string> ans;

int main() {
	fastio;
	int L, C;
	cin >> L >> C;
	vector<char> a;
	vector<char> b;
	char c;
	for (int i = 0; i < C; i++) {
		cin >> c;
		if (isvowel(c))a.push_back(c);
		else b.push_back(c);
	}

	vector<int> v_mask;
	vector<int> c_mask;
	v_mask.resize(a.size());
	c_mask.resize(b.size());
	for (int i = 1; L - i >= 2 && a.size() >= i; i++) {
		fill(v_mask.begin(), v_mask.end(), 0);
		fill(c_mask.begin(), c_mask.end(), 0);
		for (int j = 0; j < i; j++) {
			v_mask[a.size() - j -1] = 1;
		}
		for (int j = 0; j < L-i; j++) {
			c_mask[b.size() - j - 1] = 1;
		}

		do {
			string vowel;
			for (int k = 0; k < a.size(); k++) {
				if (v_mask[k] == 1) {
					vowel.push_back(a[k]);
				}
			}
			
			do {
				string temp = vowel;
				for (int k = 0; k < b.size(); k++) {
					if (c_mask[k] == 1) {
						temp.push_back(b[k]);
					}
				}

				sort(temp.begin(), temp.end());

				ans.push_back(temp);
			} while (next_permutation(c_mask.begin(), c_mask.end()));

		} while (next_permutation(v_mask.begin(), v_mask.end()));
	}

	sort(ans.begin(), ans.end());
	for (auto e : ans) {
		cout << e << endl;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ next_permutation 사용했습니다(메모리초과가 납니다)

dyl9912 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말