글 읽기 - c++고수님들 도와주세요..왜 시간초과가 나올까요?

sls666 3년 전 0

필요한 개수만큼 큰값부터 담은 nums배열에 대해 next_permutation을 돌리면서 최대값을 구하는 로직으로 구현을 했습니다.

백준강사님과 코드로직이 동일한데...제 코드는 왜 시간초과가 나올까요? 도와주세요...

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;

int n;
vector<string> words;
vector<char> letters; // 문자담는 배열
char alpha[300];

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		words.push_back(tmp);
		for (char c : words[i]) {
			letters.push_back(c);
		}
	}
}

int calc(vector<int>& nums) {
	int m = letters.size();
	int sum = 0;
	for (int i = 0; i < m; i++) {
		alpha[letters[i]] = nums[i];
	}
	for (string s : words) {
		int now = 0;
		for (char c : s) {
			now = now * 10 + alpha[c];
		}
		sum += now;
	}
	return sum;
}

void solve() {
	sort(letters.begin(), letters.end());
	letters.erase(unique(letters.begin(), letters.end()), letters.end());
	int m = letters.size();
	vector<int> nums;

	// 합의 최대값을 구하는 문제이므로 큰 값부터 담자. 큰 값들에 대해 최대값은 배열상태가 다를 뿐이다
	for (int i = 9; i >= 9 - m; i--) {
		nums.push_back(i);
	}
	sort(nums.begin(), nums.end());
	int ans = 0;
	do {
		int now = calc(nums);
		ans = max(ans, now);
	} while (next_permutation(nums.begin(), nums.end()));

	cout << ans << endl;
}

int main() {

	input();
	solve();

	return 0;
}

/* 백준 강사님 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
char alpha[256];
int calc(vector<string> &a, vector<char> &letters, vector<int> &d) {
    int m = letters.size();
    int sum = 0;
    for (int i=0; i<m; i++) {
        alpha[letters[i]] = d[i];
    }
    for (string s : a) {
        int now = 0;
        for (char x : s) {
            now = now * 10 + alpha[x];
        }
        sum += now;
    }
    return sum;
}
int main() {
    int n;
    cin >> n;
    vector<string> a(n);
    vector<char> letters;
    for (int i=0; i<n; i++) {
        cin >> a[i];
        for (char x : a[i]) {
            letters.push_back(x);
        }
    }
    sort(letters.begin(), letters.end());
    letters.erase(unique(letters.begin(), letters.end()), letters.end());
    int m = letters.size();
    vector<int> d;
    for (int i=9; i>9-m; i--) {
        d.push_back(i);
    }
    sort(d.begin(), d.end());
    int ans = 0;
    do {
        int now = calc(a, letters, d);
        if (ans < now) {
            ans = now;
        }
    } while (next_permutation(d.begin(), d.end()));
    cout << ans << '\n';
    return 0;
}


*/

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

문제

문제

출처

ICPC

c++고수님들 도와주세요..왜 시간초과가 나올까요?

sls666 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말