백준1213번 질문입니다!

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-K

작성

357

#include <iostream>
#include <string>

using namespace std;

string s, ret;
int cnt[200], flag;
char mid;

int main() {
	cin >> s;
	for (char a : s)cnt[a]++;
	for (int i = 'Z'; i >= 'A'; i--) {
		if (cnt[i]) {
			if (cnt[i] % 2 == 1) {
				mid = char(i); flag++;
				cnt[i]--;
			}

			if (flag == 2)break;
			for (int j = 0; j < cnt[i]; j += 2) {
				ret = char(i) + ret;
				ret += char(i);
			}
		}
	}
	// if (mid) ret.insert(ret.begin() + ret.size() / 2, mid);
	if (flag == 2) cout << "I'm Sorry Hansoo\n";
	else cout << ret << "\n";

	return 0;
}

위는 강사님이 작성해주신 코드인데

주석 처리한 insert 함수에서

어차피 ret.begin( )은 항상 0인데 반드시

넣어주어야 하는 것인지 알고싶습니다!

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
string N, R;
int e = 1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	sort(N.begin(), N.end());
	do {
		R = N;
		reverse(R.begin(), R.end());
		if (R == N) {
			cout << N;
			e = 0;
			break;
		}
	} while(next_permutation(N.begin(), N.end()));

	if(e) cout << "I'M Sorry Hansoo";

	return 0;
}

추가적으로 위는 제가 작성한 코드인데

왜 시간초과가 발생하는 것인지 잘 모르겠습니다.

C++코테 준비 같이 해요!

답변 2

박 경범

질문자

순열의 시간복잡도에 대해 생각해보았는데..

최대 O(n!)의 시간복잡도를 가지고,

문자열 최대길이가 50이니.. 그럼 최대 시간복잡도는

50!이 맞을까요?

큰돌

지식공유자

맞습니다! 50!는 너무 크기 때문에 시간초과가 나는 것이죠.

https://www.calculatorsoup.com/calculators/discretemathematics/factorials.php

이 링크를 타고 가셔서 50!가 어느정도인지 확인해주세요. ㅎㅎ

감사합니다.

큰돌

지식공유자

안녕하세요 박경범님 ㅎㅎ

예리하시네요.

근데 vector의 insert라는 함수는 다음과 같이 되어있습니다. 첫번째 인자에 iterator형이 들어가야 해요.

begin은 이터레이터이며 해당 변수의 첫번째 주소를 가리킵니다.

iterator insert (iterator position, const value_type& val);

첫번째 주소로 부터~~ 가운데 주소를 가리키기 위해서 begin() + ret / size()로 설정한 거에요.

insert를 쓰실 때는(vector)에서 꼭 begin() + n 이런식으로 쓰시는 것을 기억해주세요. 해당 부분 교안에도 추후 반영해 놓겠습니다. :) / 예를 들어 첫번째 자리에 삽입해야 한다? 그러면 begin() / 3번째 자리다? 그러면 ret.begin() + 3이겠죠?

경범님의 코드. 정말 간단한 코드인데요. 순열을 사용하셨죠?

자 근데 이 문제의 최대 문자열의 길이는 얼마일까요? 50이죠.

근데 여기서 순열을 사용하면 최대 시간복잡도는 얼마일까요?

감사합니다.

인프런 커뮤니티 질문&답변

백준1213번 질문입니다!