문제 풀이 001 - 절 대 PTA - basic - 043

저장 성
1. 원제 와 나의 방법
사고방식: 만력 알고리즘,
처음부터 P, 출력 을 찾 아 space 로 바 꾸 기;
처음부터 찾 아, A 를 찾 아...
…
매 라운드 순서대로 여섯 자 모 를 한 번 찾 고 한 자 모 를 찾 아 수정 하면 change 를 1 로 설정 합 니 다.
6 개 수정 되면 change Count 는 6,
changeCount = = 0 이면 모든 PATest 가 출력 되 었 음 을 설명 하고 종료 합 니 다.

/*
1043   PATest （20  ）
          10^4 、            。
          ，  PATestPATest.... 
       ，       。
  ，               ，
          ，         PATest      ，
          。

    ：
                10^4 、
              。

    ：
                  。        。

    ：
redlesPayBestPATTopTeePHPereatitAPPT
    ：
PATestPATestPTetPTePePee
*/
#include
#include
using namespace std;

//         ，change=0
//   ，change=1
int printAndReplace(char* str,char ch) {
	int change = 0;
	for (int i = 0; i < strlen(str); i++) {
		if (str[i] == ch) {
			cout << ch;
			str[i] = ' ';
			break;
			change = 1;
		}
	}
	return change;
}

int main()
{
	char str[10000] ;
	cin >> str;
	char pta[] = "PATest";
	
	while (true) {
		int changeCount = 0;
		for (int i = 0; i < 6; i++) {
			changeCount += printAndReplace(str, pta[i]);
		}
		if (changeCount = 0)
			break;
	}
	system("pause");
	return 0;
}

2 결과 와 분석

결과: 시간 초과;장점: 직관 적 이 고 간결 한 단점: 시간 복잡 도 는 원래 O (n) 일 수 있 었 는데 나 에 의 해 O (n ^ 2)

가 되 었 다.

분석: 많은 공 부 를 했 습 니 다. 10000 글자 의 경우 문 자 는 PATest 에서 1600 번 반복 합 니 다. 그러면 저 는 이 문자열 을 1600 번 스 캔 해 야 합 니 다. 그런데 실제로 몇 번 이면 됩 니까?6 번 이면 됩 니 다. 각각 PATest 를 한 번 씩 스 캔 하여 각 자모의 수량 을 집계 한 다음 에 출력 하면 됩 니 다

최종 버 전: 한 번 스 캔 하면 사실상 한 번 스 캔 만 하면 여섯 글자 의 수량

을 통계 할 수 있다.
3 새 버 전의 코드

#include
#include
using namespace std;

int main() {
	char str[10000];
	cin >> str;

	int P = 0, A = 0, T = 0, e = 0, s = 0, t = 0;//           

	for (int i = 0; i < strlen(str); i++) {		//           
		switch (str[i]) {
		case 'P':
			P++;
			break;
		case 'A':
			A++;
			break;
		case 'T':
			T++;
			break;
		case 'e':
			e++;
			break;
		case 's':
			s++;
			break;
		case 't':
			t++;
			break;
		}
	}

	//      
	while (P != 0 || A != 0 || T != 0 || e != 0 || s != 0 || t != 0) {
		if (P != 0) {
			P--;
			cout << 'P';
		}
		if (A != 0) {
			A--;
			cout << 'A';
		}
		if (T != 0) {
			T--;
			cout << 'T';
		}
		if (e != 0) {
			e--;
			cout << 'e';
		}
		if (s != 0) {
			s--;
			cout << 's';
		}
		if (t != 0) {
			t--;
			cout << 't';
		}
	}
	//system("pause");
}