[프로그래머스] 최빈값 구하기 (JAVA)

💡 문제 

---

최빈값은 주어진 값 중에서 가장 자주 나오는 값을 의미합니다. 정수 배열 array가 매개변수로 주어질 때, 최빈값을 return 하도록 solution 함수를 완성해보세요. 최빈값이 여러 개면 -1을 return 합니다.

 

 

사용된 알고리즘 :

1. 입력된 배열을 순회하며 각 원소의 등장 횟수(빈도수)를 Map에 저장한다.

2. Map에서 최빈값을 찾아서 반환한다. 이때, 최빈값이 여러 개인 경우에는 -1을 반환한다.

 

카운트를 위해 최빈값을 찾을 때는 각 key-value 쌍을 순회하면서 가장 많이 등장한 값을 찾는다. 각 원소를 키(key)로, 등장 횟수를 값(Value)로 저장하여, 순회가 끝난 후 가장 많이 등장한 원소를 찾아 반환한다.

 

시간 복잡도: O(n)

- 입력 배열의 길이가 n이라고 할 때, 입력 배열을 순회하면서 각 요소의 빈도수를 Map에 저장하는 과정에서 시간 복잡도는 O(n)이다.

- HashMap을 이용해 각 원소의 등장 횟수를 카운트하는 데에도 O(n)의 시간이 소요된다. (최빈값을 찾는 과정)

- 이 알고리즘은 상대적으로 간단하며, 입력 크기가 작은 경우에는 효율적으로 동작한다. 그러나 입력 크기가 커질수록 더 효율적인 알고리즘이 필요해질 수 있다.

 

 

 

🖍 내 답안

---

public static int solution2(int[] arr) {
        // 빈도수를 저장할 Map
        Map<Integer, Integer> freqMap = new HashMap<>();

        // 가장 높은 빈도수와 해당하는 요소를 저장할 변수
        int maxFreq = 0;
        int mode = -1; // 최빈값이 없는 경우 -1 반환

        // 입력 배열의 각 요소에 대해 빈도수 계산
        for (int i: arr) {
            // 현재 요소의 빈도수 계산
            int freq = freqMap.getOrDefault(i, 0) + 1;

            // 빈도수 Map에 저장
            freqMap.put(i, freq);

            // 현재 요소의 빈도수가 최빈값의 빈도수보다 높은 경우
            if (freq > maxFreq) {
                // 최빈값 빈도수와 해당하는 요소 업데이트
                maxFreq = freq;
                mode = i;
            } else if (freq == maxFreq) {
                mode = -1; // 최빈값이 여러 개인 겨우 -1 반환
            }
        }

        return mode;
    }

    public static void main(String[] args) {
        // 입력 배열
        int[] arr = {1,2,3,4,4,4,5,5,6,6};

        // 최빈값 찾기
        int mode = solution2(arr);
        System.out.println("최빈값: "+mode);
    }
}

 

 

for문으로 구현

public int solution1(int[] sides) {
        // 최빈값, 값별 갯수 저장, 최대값
        int[] max = new int[1001];
        int answer = 0; // 최빈값

        // 최빈값 구하기
        for (int i : sides) {
            if (sides.length != 1) {
                if (sides[i] == sides[i + 1]) {
                    //max[sides[i]];

                }
            }
            else { answer = sides[i]; }
        }

        // 최빈값 중복 확인
        int temp = 0;
        for(int i : sides) {
           // if(max[i] == frequent[j]) temp++;
            if(temp > 1) answer = -1;
        }
        return answer;
}