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

안녕하세요 1209님 ㅎㅎ

이 링크는 답지 12행에 있는 if(cnt[i])가 아니라 while(cnt[i)로 바꾸고 이에 맞춰, 18-20행을 바꿔보았습니다.

제출하게되면, 시간초과가 나는데 while을 이용한 제 코드의 시간복잡도는 얼마인가요..?

>> 그렇게 많지는 않지만 이 문제 자체가 시간초과 상한선이 낮은 것같습니다. 최대치로 계산하면 26 25정도 됩니다. (알파벳 전체탐색 [곱하기] while문 최대치 구동 횟수)

http://boj.kr/1cb106485f6b478ab640c60a6dda5cc0

전에 제가 cnt배열크기를 26이 아닌 200으로 설정한 이유를 여쭤봤었는데, 답변으로 26으로 설정해도 되며 강사님께서 200으로 설정한 이유는 크게 잡기 위해서라고 하셨습니다.

하지만, 링크를 실행하게되면 배열크기를 26, 30으로 잡고했더니 시간초과가 뜹니다.

배열크기를 60, 70으로 설정하면 메모리 초과로 뜹니다. 배열크기를 100으로 해야 정답입니다 라고 뜹니다.

>> 이 문제는 첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

대문자만이 나오는 문제입니다.

대문자는 아스키코드로 어떤 범위를 가질까요?

65 ~ 90의 범위를 가집니다. 그렇기 때문에 아스키코드를 담기 위한 100의 범위가 필요한 것이죠. (해당부분은 교안 다시 참고 부탁드립니다.)

다만 26으로도 배열을 만들어서할 수 있습니다.

이렇게 만들면 됩니다.

#include<bits/stdc++.h> 
using namespace std; 
string s, ret; 
int cnt[26], flag; 
char mid;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	for(char a : s)cnt[a - 'A']++;
	for(int i = 'Z'; i >= 'A'; i--){
		char temp = i - 'A'; 
		if(cnt[temp]){
			if(cnt[temp] & 1){
				mid = char(temp+ 'A');flag++;
				cnt[temp]--;
			}
			if(flag == 2)break;
			for(int j = 0; j < cnt[temp]; j += 2){
				ret = char(temp + 'A') + ret; 
				ret += char(temp + 'A');
			}
		}
	}
	if(mid)ret.insert(ret.begin() + ret.size() / 2, mid);
	if(flag == 2)cout << "I'm Sorry Hansoo\n";
	else cout << ret << "\n"; 
}

감사합니다.