글 읽기 - 왜 통과하는지 알고싶습니다

disdong123 3년 전 1

아래 코드가 입력

10
A
B
C
D
E
F
G
H
I
J

에 대해서 콘솔창에 실행해보면 결과를 보는것에 매우 오래걸립니다. 근데 실제로 백준에 넣어보면 통과하는데, vs의 콘솔에서 걸리는 시간은 실제 실행시간과는 전혀 상관없는건가요?

또한, 시간 복잡도도 최악의 경우, 0 ~ 9까지 모든 수를 할당하고 permutation하므로 10!, 내부 이중 포문이 최대 10 * 8

이므로 총 10! * 10 * 8 = 2억9천만으로 시간초과가 되는것같은데 제가 잘못계산한건가요?

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <climits>
#include <cstdlib>
#include <map>
//#include <bits/stdc++.h>
using namespace std;


int n;
string str[11];
map<char, int> m;
vector<char> v;
vector<int> w;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str[i];
		for (int j = 0; j < str[i].size(); j++) {
			if (!m[str[i][j]]) {
				v.push_back(str[i][j]);
				m[str[i][j]] = -1;
			}
		}
	}

	for (int i = 9; i >= 10 - v.size(); i--) {
		if (i == -1) break;
		w.push_back(i);
	}

	//reverse(w.begin(), w.end());
	int sum = 0, ans, MAX = 0;
	do {
		/*for (int i = 0; i < w.size(); i++) cout << w[i] << " ";
		cout << endl;*/
		ans = 0;
		for (int i = 0; i < v.size(); i++) {
			m[v[i]] = w[i];
		}

		for (int i = 0; i < n; i++) {
			sum = 0;
			//sum = m[str[i][0]];
			for (int j = 0; j < str[i].size(); j++) {

				sum = sum * 10 + m[str[i][j]];
			}
			//cout << sum << " ";
			ans += sum;
		}
		//cout << ans << endl;
		MAX = max(ans, MAX);
	} while (prev_permutation(w.begin(), w.end()));
	cout << MAX << endl;
}

eric00513 3년 전 0

컴퓨터가 대략 1억 번의 계산이 1초 내에 가능하다고 생각을 하고 시간복잡도를 계산하지만, 실제로는 경우에 따라 더 많은 연산이 1초에 가능합니다. 따라서 2억 9천만 번의 연산도 2초 안에 통과가 가능할 수 있습니다.

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

문제

문제

출처

ICPC

왜 통과하는지 알고싶습니다

disdong123 3년 전 1

eric00513 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말