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

 

문자를 입력받고 가장 많이 사용된 알파벳을 출력해주는데 만약 가장 많이 사용된 알파벳이 여러개 있다면 ?를 출력해주면 된다.

 

처음에 map을 사용하여 풀어서 정답이었지만 다음과 같은 문제점이 있어서 코드를 수정해보았다.

 

• map<char, int> 대신 array 사용
  • map은 내부적으로 Red-Black Tree 구조를 사용하여 삽입과 조회가 O(log N) 소요됨.
  • 하지만 알파벳 개수는 26개로 고정되어 있으므로, 배열(array<int, 26>)을 사용하면 O(1)으로 빠르게 접근 가능.
• tolower() 변환 시 불필요한 중복 연산 제거
  • 현재 tolower()를 여러 번 호출하고 있지만, 한 번 변환한 후 바로 인덱스로 사용하면 중복 연산 감소.
• 최댓값 찾기 및 중복 체크를 하나의 반복문으로 수행
  • 현재는 두 개의 반복문을 사용하여 최댓값과 중복 여부를 검사 (O(N) + O(26))
  • 한 번의 반복문(O(26))으로 최댓값과 중복 여부를 처리하여 최적화 가능

 

 

정답코드(map사용)

#include <iostream>
#include <cctype>
#include <map>

using namespace std;

map<char, int> m;
int main()
{
	string s;
	cin >> s;
	
	for (int i = 0;i < s.length();i++)
	{
		m[tolower(s[i])]++;
	}
	
	int max_value = m[s[0]];
	char max_char = s[0];
	int cnt = 0;

	for (const auto& pair : m) {
		if (max_value < pair.second)
		{
			max_value = pair.second;
			max_char = pair.first;
		}
	}

	for (const auto& pair : m) {
		if (max_value == pair.second)
		{
			cnt++;
		}
	}

	if (cnt > 1)
	{
		cout << "?";
	}
	else
	{
		cout << char(toupper(max_char));
	}
}

 

정답코드(효율적, Array사용)

#include <iostream>
#include <array>

using namespace std;

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

    array<int, 26> freq = { 0 }; // 알파벳 개수(26) 만큼 배열 생성 및 초기화

    // 문자 개수 세기
    for (char c : s)
    {
        freq[tolower(c) - 'a']++;
    }

    // 최댓값 찾기 & 중복 체크
    int max_value = 0, max_index = -1;
    bool is_duplicate = false;

    for (int i = 0; i < 26; i++)
    {
        if (freq[i] > max_value)
        {
            max_value = freq[i];
            max_index = i;
            is_duplicate = false; // 새로운 최댓값이 나오면 중복 여부 초기화
        }
        else if (freq[i] == max_value)
        {
            is_duplicate = true;
        }
    }

    // 출력
    if (is_duplicate)
        cout << "?";
    else
        cout << char(max_index + 'A'); // 대문자로 변환

    return 0;
}