[백준 C++] 1157번 - 단어공부

1157번 - 단어 공부

 

<코드 작성>

1. 문자열 입력받기
2. 문자열의 길이만큼 동적 배열 할당받기(알파벳 개수를 체크하기 위함)
3. 이중 for문을 통해 입력된 알파벳의 중복 개수 확인하기, 대문자로 비교하기 위해 toupper사용
4. for문을 통해 가장 많이 사용된 알파벳 찾기
5. if문을 통해 가장 많이 사용된 알파벳이 하나일 경우와 여러 개일 경우를 구분
6. delete 하기 

 

#include <iostream>
#include <string>
#include <cctype>  //toupper사용을 위해
using namespace std;

int main() {
	string str, re;  //입력 문자열, 출력 문자열
	cin >> str;

	int cnt = 0, max = 0, max_cnt = 0;
	int n = str.length();
	int* str_cnt = new int[n];  //입력받은 문자열의 길이와 같은 배열크기를 가진 배열 선언(동적할당)

	for (int i = 0; i < str.length(); i++) {  //시간초과,,,,, 이중 for문을 없애야 하나....???
		cnt = 0;
		for (int j = i; j < str.length(); j++) {	
			if (toupper(str[i]) == toupper(str[j])) { //대문자 비교
				cnt++;  //같은 문자일 경우 1씩 증가
			}
		}
		str_cnt[i] = cnt; 
		if (max < cnt) max = cnt;  //최대 빈도수 체크 
	}
	
	for (int i = 0; i < str.length(); i++) {
		if (max == str_cnt[i]) {
			max_cnt++;  //최대 빈도수가 중복될 경우를 체크 
			re = toupper(str[i]);  //최종 출력될 문자
		}
	}
	
	if (max_cnt != 1) cout << "?";  //최대 빈도수의 문자가 유일하지 않을 경우
	else cout << re;   //최대 빈도수의 문자가 유일할 경우 

	delete[] str_cnt;  //동적할당을 했으면 무조건 delete
	return 0;
}

이렇게 코드를 작성하여 제출할 경우,

시간 초과가 발생합니다.

시간초과

처음에는 출력할 때 endl대신 \n을 사용해 봤지만 계속 시간초과가 떠서 이중 for문을 없애는 방법으로 코드를 수정하였습니다. 

이중 for문을 없애기 위해 문자열의 문자 자체로 비교하는 방식 대신 문자열의 index를 사용하여 비교하는 방식으로 코드를 수정했습니다. 

이 과정에서 알파벳 종류만큼 배열(alpha_cnt)을 선언하였습니다. 

알파벳이 소문자일 경우 65를 빼서 그 값을 alpha_cnt의 인덱스로 사용하여 해당 값을 1씩 증가하였습니다. (아래 코드의 첫 번째 for문 참고)

그리고 최종적으로 가장 많이 사용된 알파벳을 확인할 때도 alpha_cnt 배열의 값으로 비교해 해당 index값을 max_index에 대입하였습니다. (아래 코드의 두 번째 for문 참고)

마지막으로 위의 코드와 동일하게 if문을 사용하여 최대 빈도수를 가지는 알파벳이 하나일 경우와 여러 개일 경우를 분리하였습니다. 

 

↓

<수정한 코드> - index값을 사용하여 비교 

#include <iostream>
#include <string>
using namespace std;

int main() {
	string str;
	cin >> str;

	int alpha_cnt[26] = { 0, };
	int cnt = 0, max = 0, max_index = 0;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] < 97) {  //소문자일 경우 
			alpha_cnt[str[i] - 65]++;
		}
		else {  //대문자일 경우 
			alpha_cnt[str[i] - 97]++;
		}
	}

	for (int i = 0; i < 26; i++) {
		if (max < alpha_cnt[i]) {  //가장 많이 사용된 알파벳 index찾기
			max = alpha_cnt[i];
			max_index = i;  //최대 빈도수 index
		}
	}

	for (int i = 0; i < 26; i++) {  //최대 빈도수의 중복 찾기 
		if (max == alpha_cnt[i]) cnt++;
	}

	if (cnt != 1) cout << "?";  //최대 빈도수의 중복이 일어날 경우 
	else cout << (char)(max_index + 65);  //최대 빈도수가 유일할 경우 
	return 0;
}

 

처음 코드를 작성할 때, 가장 많이 사용된 알파벳을 찾기 위해 각각의 알파벳을 비교해야 한다는 생각만 했습니다. 

그러다 보니 이중 for문을 사용하게 되었고, 계속 시간 초과가 나왔던 것 같습니다. 

string으로 문자열을 입력받은 이유도 문자 하나하나를 편하게 비교하기 위함이었습니다. 앞으로는 알파벳이나 기호 등을 비교하는 문제에서는 문자를 직접 비교하는 방법과 index를 사용한 비교 방법을 적절하게 판단하여 사용해야겠다는 생각을 하게 되었습니다. 

 

감사합니다.

2021.12.31