[Programmers : Java] 최빈값 구하기

🎯 Programmers 120812 — 최빈값 구하기

📌 문제 링크: 프로그래머스 120812 - 최빈값 구하기

---

📘 문제 요약

정수 배열 array가 주어질 때, 가장 자주 등장한 수(최빈값)를 반환하시오.
단, 최빈값이 여러 개면 -1을 반환합니다.

---

💡 1️⃣ 배열 기반 풀이

 

 

class Solution {
    public int solution(int[] array) {
        int[] numCnt = new int[1000]; // 빈도 카운팅용 배열
        int max = -1;

        // 1단계: 각 숫자의 빈도 세기 + 최대 빈도 찾기
        for (int i = 0; i < array.length; i++) {
            numCnt[array[i]]++;
            if (numCnt[array[i]] > max) {
                max = numCnt[array[i]];
            }
        }

        // 2단계: 최빈값이 여러 개인지 확인
        int cnt = 0;
        int maxIndex = 0;
        for (int i = 0; i < numCnt.length; i++) {
            if (numCnt[i] == max) {
                cnt++;
                maxIndex = i;
            }
            if (cnt > 1) return -1; // 여러 개면 -1
        }

        return maxIndex;
    }
}

---

✅ 장점

1. 빠른 속도
   • 배열의 인덱스로 직접 접근하므로 해시 연산이 필요 없음
   • 시간 복잡도: O(N + K)
     (N: 배열 크기, K: numCnt 배열 크기 = 1000으로 상수)
2. 단순하고 직관적
   • 별도의 자료구조 없이 기본 for문으로만 구현 가능
3. 메모리 접근이 연속적이라 캐시 효율이 높음

---

❌ 단점

1. 숫자 범위 제한
   • int[] numCnt = new int[1000]; 처럼 미리 범위를 알아야 함
   • 만약 입력값이 10000이나 음수라면 코드 수정 필요
2. 확장성 부족
   • 데이터 크기나 범위가 가변적이면 코드 유지보수가 어려움
3. 의미 해석이 어려움
   • numCnt[숫자]++ 구조는 초보자에게 직관적이지 않을 수 있음

---

💡 2️⃣ HashMap 기반 풀이

 

import java.util.*;

class Solution {
    public int solution(int[] array) {
        Map<Integer, Integer> cntMap = new HashMap<>();
        
        // 각 숫자의 빈도 세기
        for (int num : array) {
            cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
        }

        int highestValue = -1;
        int highestIndex = -1;
        boolean flag = false;
        
        // 최빈값 찾기
        for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {
            if (entry.getValue() > highestValue) {
                highestValue = entry.getValue();
                highestIndex = entry.getKey();
                flag = false;
            } else if (entry.getValue() == highestValue) {
                flag = true;
            }
        }

        return flag ? -1 : highestIndex;
    }
}

---

✅ 장점

1. 범위 제한 없음
   • 숫자의 크기가 커도, 음수여도, 중복이 많아도 문제없음
2. 가독성 좋음
   • cntMap.getOrDefault(num, 0) 등 자바스럽고 의미가 명확
3. 유연한 확장성
   • 문자열, 음수, 객체 등 어떤 타입으로도 확장 가능
   • 이후 정렬이나 다른 통계 처리도 쉽게 추가 가능

---

❌ 단점

1. 상대적으로 느림
   • HashMap의 해시 연산 및 오토박싱 비용이 있음
   • 시간 복잡도: O(N) (평균), 단 해시충돌 시 O(N^2)까지 가능
2. 메모리 사용량 증가
   • 객체 구조(HashMap Entry 등)로 인해 배열보다 메모리 낭비
3. 비교적 복잡한 구문
   • 초보자 입장에서 entrySet()이나 getOrDefault()가 생소할 수 있음

---

⚙️ 3️⃣ 두 코드의 비교

구분배열 기반HashMap 기반

시간 복잡도	O(N + K) (상수배 빠름)	O(N) (평균)
공간 복잡도	O(K) (1000개 고정)	O(N) (입력 크기만큼)
입력 범위 제한	있음 (0~999 가정)	없음
가독성	중간 (index 직접 관리)	높음 (명시적 구조)
확장성	낮음	높음
메모리 효율	좋음	나쁨
코테 적합도	✅ 빠르고 단순 (적합)	⚪ 유연하지만 살짝 무겁음

---

🧾 4️⃣ 평가 및 결론

상황추천 방식

✅ 입력값이 작고 범위가 정해져 있음	배열 기반이 압도적으로 빠름
⚙️ 입력값이 클 수도 있고 범위를 모름	HashMap 기반이 안전하고 유지보수 용이
📊 코딩테스트 문제	배열 기반 (성능 중심)
🧩 실무/프로젝트 코드	HashMap 기반 (가독성 중심)

---

✨ 결론 요약

🔹 배열 기반 코드는 “작고 확실한 입력”일 때 최고 효율을 낸다.
🔹 HashMap 기반 코드는 “유연하고 범위가 불확실한 입력”에 강하다.
🔹 **성능 중심(코테)**이라면 배열,
🔹 **유지보수 중심(실무)**이라면 HashMap을 선택하자.

---

💬 Tip:
만약 숫자 범위를 모른다면,
HashMap으로 작성한 뒤 성능이 중요해지는 상황에서만 배열로 최적화하는 것이 베스트 전략입니다.