[1일1백준 : 1157번] 단어 공부

문제만 봐서는 생각보다 간단해보였는데 막상해보니 엄청 어려웠던 것 같다..

3일동안 게속 시도 끝에 풀 수 있었다..

 

처음에는 이중for문을 사용했는데, 결과는 같으나 시간초과가 떳다..

그래서 2중 for문을 안쓰면서 같은 결과가 나오게끔 다시 설계를 했다..

 

이중 for문을 이용한 방식 (O(n^2)이라 시간 초과가 떳음..)

#include <iostream>
#include <vector>
#include <algorithm>

/*
* 
A ~ Z : 65 ~ 90
a ~ z : 97 ~ 122

tolerance : 32
ASCII Code Chart : https://t1.daumcdn.net/cfile/tistory/2704094E5269503021

*/

/// <summary>
/// 문제에 보면 중복되는 문자까지도 동일하게 취급을 해야되기 때문에 이를 동일시 해주는 함수를 만듬
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
const int Standardization(const int number)
{
	if (number <= 90)
	{
		return number + 32;
	}
	return number;
}

int main(void)
{
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	std::string str;
	std::cin >> str;
	int strSize = str.size();

	std::vector<int> index(strSize);

	for (size_t i = 0U; i < strSize; i++)
		index[i] = (int)str[i];


	std::vector<int> max_container;
	max_container.reserve(2);

	int max = 0, prev_max = 0, max_idx = 0, idx = 0;
	for (size_t i = 0; i < strSize; i++)
	{
		max = 0;
		idx = Standardization(index[i]);
		for (size_t j = 0; j < strSize; j++)
		{
			if (idx == Standardization(index[j]))
			{
				if (i == 0)
					prev_max++;
				else {
					max++;
				}
			}
		}

		if (max > prev_max)
		{
			prev_max = max;
			max_idx = i;
		}
		else if (max == prev_max)
		{
			if (std::find(max_container.begin(), max_container.end(), index[i]) == max_container.end()) {
				max_container.emplace_back(Standardization(index[i]));
			}
		}
	}

	if (max_container.size() > 1)
	{
		std::cout << "?" << "\n";
	}
	else {
		std::cout << (char)(index[max_idx] >= 97 ? index[max_idx] - 32 : index[max_idx]) << "\n";
	}


	return 0;
}

 

 

O(n)의 방식

#include <iostream>
#include <vector>

/*
* 
A ~ Z : 65 ~ 90
a ~ z : 97 ~ 122

tolerance : 32
ASCII Code Chart : https://t1.daumcdn.net/cfile/tistory/2704094E5269503021

*/

/// <summary>
/// 문제에 보면 중복되는 문자까지도 동일하게 취급을 해야되기 때문에 이를 동일시 해주는 함수를 만듬
/// </summary>
/// <param name="number"></param>
/// <returns></returns>
const int Standardization(const int number)
{
	if (number <= 90)
	{
		return number + 32;
	}
	return number;
}

typedef struct DataSet
{
	DataSet() = default;
	DataSet(int data, int Count) : data(data), Count(Count) {}
	int data;
	int Count;
};

int main(void)
{
	std::string str;
	std::vector<DataSet> index(1000000);
	std::vector<int> caseIndex;
	
	
	std::cin >> str;

	int strSize = str.size();
	index.reserve(strSize);
	caseIndex.reserve(strSize);

	for (auto& v : str)
	{
		int ANCII = Standardization(v);
		index[ANCII] = DataSet(ANCII, 0);
		caseIndex.emplace_back(ANCII);
	}

	for (size_t i = 0; i < caseIndex.size(); i++)
	{
		int ANCII = caseIndex[i];
		int data = index[ANCII].data;

		index[ANCII].Count++;
	}
	int max = 0, max_idx = 0;
	for (size_t i = 0; i < caseIndex.size(); i++)
	{
		int ANCII = caseIndex[i];
		if (max < index[ANCII].Count) {
			max = index[ANCII].Count;
			max_idx = i;
		}
	}

	bool IsSame = false;
	for (size_t i = 0; i < caseIndex.size(); i++)
	{
		int ANCII = caseIndex[max_idx];
		if (index[caseIndex[i]].data == ANCII)
			continue;
		if (index[ANCII].Count == index[caseIndex[i]].Count)
		{
			IsSame = true;
			break;
			
		}
	}
	char result = (IsSame) ? '?' : (char)((caseIndex[max_idx] >= 97) ? caseIndex[max_idx] - 32 : caseIndex[max_idx]);
	std::cout << result << "\n";
		



	return 0;
}

1157번: 단어 공부 (acmicpc.net)

1157번: 단어 공부