#1157 단어 공부

# 문제

# 입력 및 출력

# 풀이

예전에 자바로 풀었다가 메모리 초과 떠서 해결하지 못한 상태로 넘어간 문제였다

c++로 풀었을 때 한번에 해결하긴 했는데 좀 더 코드를 줄일 수 있을 것 같아서 구글링해봤다

 

아래가 처음 작성한 코드다

toupper(), tolower() 기억해두기!

#include <iostream>
using namespace std;
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int aCount[26];

int main() {
	string input;
	cin >> input;
	for (int i = 0; i < input.size(); i++) {
		input[i] = toupper(input[i]);
		for (int j = 0; j < 26; j++) {
			if (alphabet[j] == input[i]) {
				aCount[j]++;
			}
		}
	}
	int maxIndex, maxValue = 0;
	bool isOnly = true;
	for (int i = 0; i < 26; i++) {
		if (aCount[i] > maxValue) {
			maxValue = aCount[i];
			maxIndex = i;
			isOnly = true;
		}
		else if (aCount[i] == maxValue) {
			isOnly = false;
		}
	}
	if (isOnly == false) {
		cout << "?" << endl;
		return 0;
	}
	cout << alphabet[maxIndex] << endl;
}

변수명이 길어서 복잡해보일 수 있으나 복잡한 코드는 아니다

 

https://cryptosalamander.tistory.com/12

[백준 / BOJ] - 1157번 단어 공부 C++ 풀이

구글링 해보니 첫번째 반복문에서 시간 복잡도를 줄일 수 있었다

#include <iostream>
using namespace std;
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int aCount[26];

int main() {
	string input;
	cin >> input;
	for (int i = 0; i < input.size(); i++) {
		input[i] = toupper(input[i]);
		aCount[input[i] - 'A']++; // 이부분으로 반복문 하나를 줄임
	}
	int maxIndex, maxValue = 0;
	bool isOnly = true;
	for (int i = 0; i < 26; i++) {
		if (aCount[i] > maxValue) {
			maxValue = aCount[i];
			maxIndex = i;
			isOnly = true;
		}
		else if (aCount[i] == maxValue) {
			isOnly = false;
		}
	}
	if (isOnly == false) {
		cout << "?" << endl;
		return 0;
	}
	cout << alphabet[maxIndex] << endl;
}

'A'를 해주면 'A'-'A'=0, 'C'-'A'=2 이런식으로 계산되기 때문에 알파벳을 찾기 위한 26번 반복하는 반복문을 줄일 수 있다

따라서 최대 2,600,000번 반복하는 코드를 최대 1,000,000로 줄였다

메모리도 더 줄은 것을 볼 수 있음