코딩테스트 Map 풀이: 학급 회장 득표수 세기

내가 푼 풀이

function solution(s) {
  let arr = s.split("");

  let obj = arr.reduce((acc, cur) => {
    acc[cur] += 1;
    return acc;
  }, { A: 0, B: 0, C: 0, D: 0, E: 0 });

  let maxKey = null;
  let maxValue = -Infinity;

  for (const key in obj) {
    if (obj[key] > maxValue) {
      maxValue = obj[key];
      maxKey = key;
    }
  }

  return maxKey;
}

이 풀이는 후보가 A~E로 고정되어 있다는 문제 조건을 코드에 직접 반영한 방식입니다. 객체를 미리 초기화해 두고, 문자열을 순회하며 각 후보의 득표 수를 누적합니다.

동작 메커니즘은 단순합니다. 문자열을 배열로 변환한 뒤, reduce를 이용해 각 문자에 해당하는 카운트를 증가시키고, 이후 한 번의 반복으로 최댓값을 가진 키를 찾습니다.

실수하기 쉬운 포인트는 초기 객체에 없는 문자가 등장할 가능성을 고려하지 않았다는 점입니다. 현재 문제에서는 조건상 문제가 없지만, 입력 조건이 조금만 바뀌면 런타임 오류 또는 잘못된 결과로 이어질 수 있습니다.

개선 방향으로는 초기 객체를 하드코딩하지 않고, 등장하는 값만 동적으로 집계하도록 구조를 바꾸는 것이 좋습니다.

정답 풀이

function solution(s) {
  let answer;
  let sH = new Map();

  for (let x of s) {
    if (sH.has(x)) sH.set(x, sH.get(x) + 1);
    else sH.set(x, 1);
  }

  let max = Number.MIN_SAFE_INTEGER;
  for (let [key, val] of sH) {
    if (val > max) {
      max = val;
      answer = key;
    }
  }

  return answer;
}

정답 풀이는 후보의 종류를 사전에 가정하지 않습니다. 문자열을 순회하면서 실제로 등장한 문자만 Map에 저장하고, 그 빈도를 누적합니다.

이 방식의 핵심은 확장성입니다. 후보가 늘어나거나 문자 종류가 변경되더라도 코드 수정 없이 그대로 동작합니다.

일반적인 JavaScript 구현에서는 각 Map 접근을 평균 상수 시간으로 보고 전체를 O(N)으로 설명합니다. 다만 명세가 특정 해시 테이블 구현이나 모든 접근의 정확한 O(1)을 보장하는 것은 아닙니다.

출제 의도

이 문제는 단순 구현 문제가 아니라, 문자열 데이터를 집계할 때 어떤 자료구조를 선택해야 하는지를 묻는 문제입니다.

이 글에서는 해시(Map)를 이용한 빈도 집계 패턴을 연습합니다. 출제자가 특정 자료구조만 요구했다고 단정하지 않고 입력 조건과 출력 결과로 풀이를 판단합니다.

문제의 입력 조건과 시간·메모리 제한을 만족한다면 초기화된 객체를 쓰는 풀이도 정답입니다. 여기서는 다른 문제로 확장하기 쉬운 빈도 집계 패턴을 익히기 위해 Map 풀이를 함께 제시합니다.

이 문제는 이후 등장하는 해시 문제들의 기초 사고를 형성하기 위한 전형적인 입문 문제로 볼 수 있습니다.

빈도 비교 문제를 한 단계 확장하려면 JS 아나그램 슬라이딩 윈도우를 함께 읽으면 흐름이 연결됩니다.

Map 동작·동률·검증 기준

득표 문자열 길이를 N, 서로 다른 후보 수를 U라고 하면 Map 풀이의 추가 공간은 빈도표 O(U), 반환 후보 하나는 O(1)입니다. 이 문제는 후보가 A~E로 고정되어 U≤5이므로 계산용 추가 공간은 O(1)로 볼 수 있습니다. 이미 전달된 입력 문자열까지 포함하면 O(N+U) 저장 공간입니다. 앞의 객체 비교 풀이는 split("")로 문자 배열도 만들기 때문에 그 배열에 O(N) 추가 공간을 사용합니다.

Map은 키와 값을 저장하고 키가 처음 삽입된 순서를 기억합니다. 따라서 현재 정답 코드는 동률이면 투표 문자열에서 먼저 처음 등장해 Map에 삽입된 후보를 반환합니다. 문제가 유일한 최다 득표자를 보장하지 않는다면 사전순, 공동 우승자 배열, 재투표 같은 동률 규칙을 별도로 정해야 합니다.

JavaScript 명세는 Map 접근 시간이 원소 수에 대해 평균적으로 선형보다 빨라야 한다고 요구하지만, 내부 구현이 반드시 해시 테이블이거나 모든 연산이 정확히 O(1)이라고 보장하지는 않습니다. 코딩 테스트에서는 일반적인 구현을 전제로 전체 순회를 O(N)으로 설명하되, 이 구분은 MDN Map 문서와 함께 적는 편이 정확합니다.

console.assert(solution('BACBACCACCBDEDE') === 'C');
console.assert(solution('AB') === 'A'); // 현재 구현의 동률 규칙: 먼저 삽입된 후보
console.assert(solution('') === undefined); // 빈 입력 정책을 호출부에서 결정

빈 문자열에서는 answer가 정해지지 않아 undefined를 반환합니다. 문제 입력이 최소 한 표를 보장하면 괜찮지만, 범용 함수라면 빈 입력에서 오류를 낼지, null을 반환할지 명시하세요.

A~E만 나온다는 현재 조건에서는 초기값을 가진 일반 객체 풀이도 정확합니다. 후보가 동적으로 늘어나면 Map은 별도 초기화 없이 키를 추가할 수 있고, 문자열뿐 아니라 다른 타입도 키로 사용할 수 있다는 장점이 있습니다. 객체로 일반화한다면 상속된 프로퍼티와 사용자 입력 키가 충돌하지 않도록 Object.create(null) 또는 소유 프로퍼티 검사도 고려해야 합니다.

입력 검증 역시 자료구조 선택과 별개입니다. 허용되지 않은 기호를 무시할지 오류로 처리할지, 대소문자를 같은 후보로 볼지, 공백을 투표로 셀지를 정하지 않으면 같은 함수가 호출 위치마다 다른 의미로 사용될 수 있습니다.

정리: 빈도 집계는 ‘키가 늘어나도 코드가 바뀌지 않는가’뿐 아니라 빈 입력과 동률을 어떻게 처리하는지까지 정해야 완성됩니다. 이 세 조건을 테스트에 고정하면 후보 종류가 바뀌어도 안전하게 재사용할 수 있습니다. 특히 동률 규칙은 구현의 우연한 순서에 맡기지 말고 요구사항 이름으로 테스트에 남기세요.