최빈값 구하기 JAVA 자바 코팅테스트 프로그래머스

최빈값 구하기 JAVA

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

코딩테스트 연습 | 프로그래머스 스쿨

 

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

 

✒️ 제한사항 :

• 0 < array의 길이 < 100
• 0 ≤ array의 원소 < 1000

이 문제는 mode (최빈값) 알고리즘 문제 였다. 그리고.. 최빈값이 여러개일 때는 -1을 return하는 것이 추가된 형태인데.. 최빈값 구하는 알고리즘만대로 코드를 작성하니, 코드를 실행 했을 때는 통과가 되지만 제출을 하면 통과하지 못했다.

---

코드 실행에만 통과했던 코드 :

class Solution {
    public int solution(int[] array) {
        int mode = 0;
        int[] index = new int[array.length+1]; // 마지막 값에서 검색 할 때, 인덱스 범위 오류 때문에 +1
        int max = Integer.MIN_VALUE; // 최대값 저장, 초기값은 정수형의 최소값으로 지정.
        
        for(int i=0; i<array.length; i++){
           index[array[i]]++;
        }
        
        for(int i=0; i<index.length; i++){
            if( max<index[i] ){ 
                max = index[i]; // 최대값
                mode = i ; // mode:최빈값 
            } else if(max == index[i]) { // 여러개인지
                mode = -1;
            }
        }
        
        return mode;
    }
}

이 코드로는 제출하면 실패가 엄청뜬다. 질문하기를 통해 알게된 반례를 적용했더니 에러가 빡 뜨면서 원인을 파악 할 수 있었다.

 

반례

입력값 〉 [80, 80, 80, 9, 9]
기댓값 〉 80

 

통과된 코드 : index 배열의 길이를 제한 사항에 있던 수치와 동일하게 설정했다.

 

class Solution {
    public int solution(int[] array) {
        int mode = 0;
        int[] index = new int[1000]; // index의 길이를 수정함.
        int max = Integer.MIN_VALUE; // 최대값 저장, 초기값은 정수형의 최소값으로 지정.
        
        for(int i=0; i<array.length; i++){
           index[array[i]]++;
        }
        
        for(int i=0; i<index.length; i++){
            if( max<index[i] ){ 
                max = index[i]; // 최대값
                mode = i ; // mode:최빈값 
            } else if(max == index[i]) { // 여러개인지
                mode = -1;
            }
        }
        
        
        return mode;
    }
}

 

통과는 됐지만... 어딘가 찝찝하다. 통과하고 나서 다른 분들 코드를 보니 감탄이 절로~나옴..! 그 중에서 가장 깔끔하고 이해가 쏙쏙 되는 코드를 소개해본다.

 

import java.util.*;

class Solution {
    public int solution(int[] array) {
        int maxCount = 0;
        int answer = 0;

        Map<Integer, Integer> map = new HashMap<>();

        // getOrDefault : 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드
        // getPrDefault(Object key, V DefaultValue)
        // 매개변수 : 이 메서드는 두개의 매개변수를 허용
        // key : 값을 가져와야 하는 요소의 키
        // defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값
        // 반환값 : 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환

        for(int number : array) {
            int count = map.getOrDefault(number, 0) + 1;

            if(count > maxCount) {
                maxCount = count;
                answer = number;
            }

            else if(count == maxCount) {
                answer = -1;
            }

            map.put(number, count);
        }

        return answer;
    }
}

주석 감사합니다...!! 이해가 쏙쏙쏙~!

---

 

 

최빈값 알고리즘 참고 1 : https://blog.naver.com/javaking75/140176240536

[Java] 기초알고리즘 - 06. 최빈값 (빈도수가 많은값 ;Mode) 알고리즘

 

최빈값 알고리즘 참고 2 : https://wakestand.tistory.com/599

자바 최빈값(Mode) 알고리즘 정리