[Lv.0 - Java] 120812. 최빈값 구하기

문제

 

 

 

풀이

아 솔직히 최빈값 진짜 어려웠다. 혼자 머리싸매다가 여러사람 풀이도 많이 보고 이해 안돼서ㅋㅋㅋ 끙끙앓다가 그나마 이해되고 알아듣는 방향의 코드를 참고하여 풀수 있었다.

 

1. 먼저 주어진 array 배열을 오름차순으로 정렬한다. Arrays.sort(array);

이때, Arrays.sort() 메소드를 사용하기 위해서는 import java.util.Arrays로 라이브러리를 import 해주는 것을 잊지않아야한다.

2. 정렬된 배열에서 가장 큰 값을 찾아서 변수 max에 저장한다. int max = array[array.length-1];

3. 저장한 최대값 `max` 를 이용해서 빈도수를 저장할 배열 count[] 를 생성한다. 이때, 배열의 크기는 최댓값보다 1 커야한다. (이부분에서 이해가 잠시 안됐는데, 드디어 이해를 했다. 최대값보다 1 커야하는 이유는 만약 최대값이 5라면, 반복을 5까지 해야하지만 java에서 배열의 인덱스는 0부터 시작하기 때문에 5까지 반복하기 위해서는 5+1이된 6을 배열의 크기로 줘야 하기 때문이었다.)

int[] count = new int[max+1];

4. 정렬된 배열을 이제 for문을 사용해 순회하면서 각 숫자의 빈도수를 count 배열에 기록한다. ++을 이용해서 같은 숫자가 나올때는 해당 배열의 숫자를 +1 시킨다.

(예를들면, array[1]의 숫자가 1이라면 count[1]의 값이 +1이 되어 해당 인덱스에 저장된 값이 1이 되고(초기값은 0이니까), array[2]의 숫자도 1이라면 count[1] 에 +1이 되어 해당 인덱스에 저장된 값이 1+1이 되어 count[1]의 값은 2가 되는 식이다.)

for(int i=0; i<array.length; i++){

    count[array[i]] ++;

}

5. count 배열의 첫번째 값으로 변수 top을 초기화한다. (이제 이미 count 배열에 값은 다 카운팅되어 들어갔으니 최대빈도수값을 찾으러가는거다.)

int top = count[0];

6. count 배열을 순회하면서 top(최대빈도수 값)을 찾는다.

for (int i=1; i<count.length; i++) {
7. if문을 사용해 top의 숫자가 count[i] 보다 작다면 최대빈도수가 아니므로 count[i]를 저장한다. 그리고 answer의 값을 i로 저장한다.(count[i]가 지금 현재는 제일 큰 숫자(=최대빈도수)이므로) 그렇게 계속 반복하면 가장 큰 숫자가 결국에 마지막에 저장된다. 작다면 변수 top의 값도, answer의 값도 변하지 않으므로.

            if (top < count[i]) {
                top = count[i];
                answer = i;

            }

8. 만약 for문 반복중 현재 숫자의 빈도수가 최대값과 같다면 최대값이 여러개인 경우이기 때문에 문제에 주어진 값처럼 answer에 -1을 저장하고 반환한다.

 

 

 

코드

import java.util.Arrays;

class Solution {
    public int solution(int[] array) {
        int answer = 0;
        
        Arrays.sort(array);
        int max = array[array.length-1];
        int[] count = new int[max+1];
        
        for (int i = 0; i<array.length; i++) {
                count[array[i]] ++;
        }
        
        int top = count[0];
        
        for (int i=1; i<count.length; i++) {
            if (top < count[i]) {
                top = count[i];
                answer = i;
            }else if (top == count[i]) {
                answer = -1;
            }      
        }
        return answer;
    }
}

 

 

 

++ 다른사람의 풀이를 보다보니 이런 Map을 이용한 방법도 있어서 추가해본다.

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. Map<Integer, Integer> map = new HashMap<>();  : 정수값과 해당값의 빈도수를 저장할 HashMap을 생성

2. for(int number : array) {   :   주어진 배열을 순회하면서 각 숫자의 빈도수를 계산

3. int count = map.getOrDefault(number, 0) + 1;   :   현재 숫자의 빈도수를 가져옴. 만약 해당 숫자가 맵에 없으면 기본값을 0으로 하고, 1을 더해 현재 빈도수를 증가시킨다.

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

     :   현재 숫자의 빈도수가 최대값(maxCount)보다 크다면 최대값(maxCount) 과 answer을 업데이트 한다.

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

    :   현재 숫자의 빈도수가 최대값과 같다면 최빈값이 여러개인 경우이기 때문에 answer을 -1로 설정한다.

6. map.put(number, count);   :   현재 숫자의 빈도수를 map에 업데이트 한다.