💻 1157번 문제 : 단어 공부 ➕

1157번: 단어 공부

https://www.acmicpc.net/problem/1157

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	char inputArr[1000001] = {};
	int alphabetArr[26] = {};
	int manyUseAlphabet = 0;
	char answer = 0;

	cin >> inputArr;

	for (int i = 0; i < sizeof(inputArr); i++)
	{
		if (65 <= inputArr[i] && 90 >= inputArr[i])
		{
			int temp = inputArr[i] - 65;
			alphabetArr[temp] += 1;
		}

		else if (97 <= inputArr[i] && 122 >= inputArr[i])
		{
			int temp = inputArr[i] - 97;
			alphabetArr[temp] += 1;
		}
	}
	
	for (int i = 0; i < 26; i++)
	{
		if (alphabetArr[i] == manyUseAlphabet)
		{
			answer = '?';
		}

		else if (alphabetArr[i] > manyUseAlphabet)
		{
			manyUseAlphabet = alphabetArr[i];
			answer = 'A' + i;
		}
	}

	cout << answer << '\n';
}

메모리 (KB)	시간 (ms)	코드 길이 (B)
2876	12	754

➕ 재풀이

컴파일 에러

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	char inputArr[1000005];
	int alphabetArr[26] = {};
	int manyUseAlphabet = 0;
	char answer = 0;

	cin >> inputArr;

	for (int i = 0; i < strlen(inputArr); i++)
	{
		if (65 <= inputArr[i] && 90 >= inputArr[i])
		{
			int temp = inputArr[i] - 65;
			alphabetArr[temp] += 1;
		}

		else if (97 <= inputArr[i] && 122 >= inputArr[i])
		{
			int temp = inputArr[i] - 97;
			alphabetArr[temp] += 1;
		}
	}

	int alphabetArrLength = sizeof(alphabetArr) / sizeof(int);
	
	for (int i = 0; i < alphabetArrLength; i++)
	{
		if (alphabetArr[i] == manyUseAlphabet)
		{
			answer = '?';
		}

		else if (alphabetArr[i] > manyUseAlphabet)
		{
			manyUseAlphabet = alphabetArr[i];
			answer = 'A' + i;
		}
	}

	cout << answer << '\n';
}

→ strlen()을 사용하기 위해선 #include <cstring> 헤더 파일을 추가해주어야 한다.

시간 초과

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

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	char inputArr[1000001];
	int alphabetArr[26] = {};
	int manyUseAlphabet = 0;
	char answer = 0;

	cin >> inputArr;

	for (int i = 0; i < strlen(inputArr); i++)
	{
		if (65 <= inputArr[i] && 90 >= inputArr[i])
		{
			int temp = inputArr[i] - 65;
			alphabetArr[temp] += 1;
		}

		else if (97 <= inputArr[i] && 122 >= inputArr[i])
		{
			int temp = inputArr[i] - 97;
			alphabetArr[temp] += 1;
		}
	}

	int alphabetArrLength = sizeof(alphabetArr) / sizeof(int);
	
	for (int i = 0; i < alphabetArrLength; i++)
	{
		if (alphabetArr[i] == manyUseAlphabet)
		{
			answer = '?';
		}

		else if (alphabetArr[i] > manyUseAlphabet)
		{
			manyUseAlphabet = alphabetArr[i];
			answer = 'A' + i;
		}
	}

	cout << answer << '\n';
}

→ strlen()는 시간복잡도가 O(N)이라 for문과 함께 돌게 되면 O(N^2)이 돼서 시간 초과가 난다고 한다. 다른 방법으로 변수에 담아 사용하면 된다.

int length = strlen(inputArr);

https://www.acmicpc.net/board/view/43036

틀렸습니다

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	char inputArr[1000001];
	int alphabetArr[26] = {};
	int manyUseAlphabet = 0;
	char answer = 0;

	cin >> inputArr;

	for (int i = 0; i < sizeof(inputArr); i++)
	{
		if (65 <= inputArr[i] && 90 >= inputArr[i])
		{
			int temp = inputArr[i] - 65;
			alphabetArr[temp] += 1;
		}

		else if (97 <= inputArr[i] && 122 >= inputArr[i])
		{
			int temp = inputArr[i] - 97;
			alphabetArr[temp] += 1;
		}
	}
	
	for (int i = 0; i < 26; i++)
	{
		if (alphabetArr[i] == manyUseAlphabet)
		{
			answer = '?';
		}

		else if (alphabetArr[i] > manyUseAlphabet)
		{
			manyUseAlphabet = alphabetArr[i];
			answer = 'A' + i;
		}
	}

	cout << answer << '\n';
}

자, 그렇다면 이 코드는 정답인 코드와 다른 점이 뭘까? 모르겠다면 맨 위에 있는 코드와 비교해보자.

💁

바로 배열의 초기화 차이이다.

char inputArr[1000001];을 초기화 해주지 않아 이 안에는 더미값이 들어있기 때문에 정답이 아니었다. 항상 초기화 하는 버릇을 들이도록 하자.

Uploaded by N2T