백준 1157 알파벳 카운팅 — map vs int 배열

“개수를 센다”는 문제를 보면 반사적으로 map을 꺼내게 되는데, 키가 알파벳 26자로 고정돼 있으면 이야기가 달라진다. 이 글에서는 백준 1157을 map과 int 배열 두 방식으로 각각 구현해 비교한 과정을 이야기하려 한다 — 두 구현의 코드가 어떻게 갈리는지, 그리고 키 범위가 작고 고정일 때 배열이 어떤 비용을 통째로 없애는지다.

백준 1157 — map vs int 배열

알파벳 대소문자로 이루어진 단어에서 가장 많이 사용된 알파벳을 대문자로 출력. 단, 대소문자 구분 없이 집계. 동률이면 ? 출력.

처음에는 map으로 풀었는데, 키가 알파벳 26개로 고정이라면 int 배열이 더 낫다는 걸 두 버전을 나란히 놓고 비교하면서 확인했다.

map 접근 방식 — range-for로 순회

map<char, int> m;
for (char c : str)
{
    if (c >= 'a' && c <= 'z')  // 소문자이면 대문자로 변환
        c = c - 'a' + 'A';     // ASCII 차이(32) 이용
    m[c]++;
}

int maxVal = 0;
char maxChar = '?';
bool dup = false;

for (auto& [key, val] : m)  // int 인덱스 대신 key/value 직접 순회
{
    if (val > maxVal)        { maxVal = val; maxChar = key; dup = false; }
    else if (val == maxVal)  { dup = true; }
}

cout << (dup ? '?' : maxChar) << "\n";

더 효율적인 방법 — int[26] 배열

int cnt[26] = {};               // A~Z 인덱스 0~25
for (char c : str)
    cnt[toupper(c) - 'A']++;    // 'A'=0, 'B'=1, ..., 'Z'=25

int maxVal = 0, maxIdx = -1;
bool dup = false;
for (int i = 0; i < 26; i++)
{
    if (cnt[i] > maxVal)        { maxVal = cnt[i]; maxIdx = i; dup = false; }
    else if (cnt[i] == maxVal)  { dup = true; }
}

cout << (dup ? "?" : string(1, 'A' + maxIdx)) << "\n";

	map 버전	int[26] 버전
접근 속도	O(log n)	O(1)
메모리	동적 할당	고정 104 bytes
순회 방법	range-for (key/value 쌍)	index for

toupper()

#include <cctype> 필요. 소문자 → 대문자 변환, 나머지는 그대로 반환.

toupper('a')  // 'A'
toupper('Z')  // 'Z'  (이미 대문자 → 그대로)
toupper('3')  // '3'  (숫자 → 그대로)

// if문 — ASCII 차이(32) 직접 이용
if (c >= 'a' && c <= 'z')  c = c - 'a' + 'A';

// toupper — 동일한 동작, 더 간결
c = toupper(c);

'a'(97) - 'A'(65) = 32 차이 이용. 반대는 tolower(c)

---

같은 날 함께 복기한 심화반 테스트 9문제(팰린드롬·BFS·반사 벡터·virtual 소멸자·volatile·캐시 지역성·스마트 포인터 순환 참조 등)는 이 글의 주제와 묶이지 않아 덜어냈다. 개념별로는 virtual 소멸자·스마트 포인터에 따로 정리해 두었다.

핵심 요약 — 키 범위가 작고 고정된 집계는 map보다 int 배열이 빠르다(O(log n) → O(1)). 테스트 복기에서는 virtual 소멸자, weak_ptr로 순환 참조 끊기, 행 우선 저장과 SoA의 캐시 효율까지 C++ 면접 단골 주제들의 정답 근거를 다시 확인했다.