배지 개수를 모두 다르게 만드는 최소 삭제 수
자바스크립트 코딩테스트 문제로 frequency-greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
배지 이름이 담긴 배열 badges가 주어집니다.
필요하다면 일부 배지를 삭제해서, 남아 있는 각 배지 종류의 등장 횟수가 모두 서로 다르게 만들어야 합니다.
이때 삭제해야 하는 배지의 최소 개수를 반환하는 minDeletionsForUniqueBadgeCounts 함수를 작성하세요.
배지 종류 자체를 없애는 것도 가능합니다. 즉, 어떤 배지의 등장 횟수를 0으로 만들 수 있습니다.
제한사항
badges의 길이는0이상10,000이하입니다.- 각 배지 이름은 길이
1이상20이하의 문자열입니다. - 배지 이름은 대소문자를 구분합니다.
- 삭제는 배열의 원소 하나를 제거하는 것으로 봅니다.
- 남아 있는 배지 종류들의 등장 횟수만 서로 달라야 합니다.
- 반환값은 필요한 최소 삭제 횟수입니다.
예시
- 입력:
["A", "A", "A", "B", "B", "C"]→ 출력:0 - 입력:
["A", "A", "B", "B", "C", "C"]→ 출력:3 - 입력:
["A", "A", "B", "B", "C"]→ 출력:2 - 입력:
["A", "B", "C", "D"]→ 출력:3 - 입력:
[]→ 출력:0
힌트
- 먼저 배지 이름별 등장 횟수를 세어 보세요.
- 이미 사용한 등장 횟수를
Set으로 관리하면 중복 여부를 빠르게 확인할 수 있습니다. - 어떤 빈도가 이미 쓰였다면, 그 빈도를 1씩 줄이며 아직 쓰이지 않은 빈도를 찾으면 됩니다.
해설
이 문제는 배지 이름 자체보다 각 이름이 몇 번 등장했는지가 중요합니다.
예를 들어 ["A", "A", "B", "B", "C", "C"]의 빈도는 2, 2, 2입니다. 세 종류가 모두 2번씩 나오므로 그대로는 조건을 만족하지 않습니다.
한 종류는 2개를 유지하고, 다른 한 종류는 1개만 남기고, 마지막 한 종류는 모두 삭제하면 빈도는 2, 1이 됩니다. 이때 삭제 수는 0 + 1 + 2 = 3입니다.
풀이 순서는 다음과 같습니다.
- 해시 맵으로 배지별 등장 횟수를 셉니다.
- 등장 횟수들을 배열로 꺼내 큰 값부터 처리합니다.
- 이미 사용한 빈도라면, 삭제 수를 1 늘리면서 빈도를 1 줄입니다.
- 빈도가
0이 되면 그 배지 종류는 사라진 것이므로 사용한 빈도에 넣지 않습니다. - 빈도가
1이상이고 아직 사용되지 않았다면Set에 기록합니다.
큰 빈도부터 처리하면 큰 그룹을 최대한 보존할 수 있고, 작은 그룹이 필요한 만큼 줄어들어 중복을 피하게 됩니다. 같은 빈도를 만들 수 없을 때까지 줄이는 과정에서 줄어든 양이 곧 삭제한 배지 수입니다.
예를 들어 빈도가 2, 2, 1이라면 첫 번째 2는 유지합니다. 두 번째 2는 이미 사용되었으므로 1로 줄입니다. 하지만 1도 기존에 있으므로 다시 0까지 줄어야 합니다. 따라서 총 2개를 삭제해 빈도 2, 1만 남깁니다.
시간 복잡도는 배지 수를 n, 서로 다른 배지 종류 수를 m이라고 할 때 빈도 계산에 O(n), 빈도 정렬에 O(m log m)이 걸립니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.