2024. 06. 11 문제풀이

저번 글 업로드가 안되어있었다는 걸 좀전에 봤다. 암튼! 오늘의 첫 문제다.

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

또 다시 배열 문제인데 이번에야말로 값을 하나하나 다 열어봐야하는 문제이지 않을까 생각한다. 최빈값을 구하려면 어떻게 해야될까? 또 array에 그런걸 구해주는 기능이 있을까?

아무래도 그런건 없는 것 같다 문제풀이밖에 없는 걸 보니까 내가 직접 구해야한다.

일단 저번 문제 풀이에 사용했던 정렬을 쓰고 생각해봐야겠다.

class Solution {
    public int solution(int[] array) {
        int answer = 0;
        int max = 0;
        Arrays.sort(array); // 배열 정렬
        max = array[array.length - 1]; // 배열의 최댓값 찾기

        int count[] = new int[max + 1]; // 카운트 배열 생성
        for (int i = 0; i < array.length; i++) {
            count[array[i]]++; // 배열 채우기
        }
        // 최빈값 찾고 중복 -1 리턴
        max = count[0];
        for (int i = 1; i < count.length; i++){
            if(max < count[i]){
                max = count[i];
                answer = i;
            }
            else if (max == count[i]){
                return -1;
            }
        }

            return answer;
    }
}

솔직히 전혀 모르겠어서 블로그 참고하면서 코드를 썼다. 써놓고도 뭔지 잘 모르겠는데 정답도 아니다. 테스트 케이스도 통과가 안됐을 뿐더러, 점수도 65점 정도 나왔다. (반절 이상은 통과 하긴 했다.)

일단 근본적으로 아마 틀려먹었으리라.

구글링해서 좀 돌아다니다 보니까 Map이라는 게 있던데 한번 활용해볼까 싶다.

일단 Map이 뭔지 알아보자

Map은 Java에서 키와 값의 쌍을 저장하는 데이터 구조다. Map은 중복된 키를 허용하지 않으며 각 키는 정확히 하나의 값을 가진다. 키를 사용하여 값을 효율적으로 검색, 추가, 수정, 삭제할 수 있다. Map 인터페이스는 Java Collections Framework의 일부이며, 여러 가지 구현 클래스가 있다.

주요 구현 클래스

1. HashMap

가장 일반적으로 사용되는 Map 구현이다.
키와 값의 쌍을 해시 테이블에 저장하며, 해시 함수로 검색 성능을 최적화한다.
순서를 보장하지 않는다.

2. LinkedHashMap

HashMap과 유사하지만, 삽입 순서를 유지한다.
키와 값의 쌍을 링크드 리스트로 연결하여 순서성을 제공한다.

3. TreeMap

키를 정렬된 순서로 저장한다.
내부적으로 이진 검색 트리(Red-Black 트리)를 사용하여 정렬을 유지한다.
키의 자연 순서나 제공된 비교자(Comparator)를 사용하여 정렬한다.

4. Hashtable

HashMap과 유사하지만, 동기화된 메서드를 제공한다.
레거시 클래스이며, 새로운 코드에서는 일반적으로 사용되지 않는다.

주요 메서드

• put(K key, V value): 키와 값의 쌍을 Map에 추가한다.
• get(Object key): 키에 해당하는 값을 반환한다.
• remove(Object key): 키에 해당하는 값을 제거한다.
• containsKey(Object key): 키가 Map에 존재하는지 확인한다.
• containsValue(Object value): 값이 Map에 존재하는지 확인한다.
• size(): Map의 크기를 반환한다.
• isEmpty(): Map이 비어 있는지 확인한다.
• keySet(): Map의 모든 키를 반환한다.
• values(): Map의 모든 값을 반환한다.
• entrySet(): Map의 모든 키-값 쌍을 반환한다.

챗 지피티한테 맵에 대해 정리해달라고 해서 나온 결과고 당연 나는 무슨소리인지 이해는 어렴풋이 된다.

음 근데 풀이를 한번 대강 보니까 Map쪽이 훨씬 더 이해가 안된다. 그냥 풀던대로 풀어야겠다.

아니다 그냥 두개 다 답안을 올려서 해석하는편이 지금의 나로썬 최선의 공부방법인 것 같다 지금 고민하는 시간만 거의 3시간이기 때문에 시간을 더 쓸 수는 없다. (약속 때문에 나가야된다 ㅠㅠ)

일단 if와 for을 사용했을 때의 최빈 값 찾기다.

class Solution {
    public int solution(int[] array) {
        Arrays.sort(array); // 배열을 오름차순으로 정렬

        int mostFrequentValue = array[0]; // 최빈값을 저장할 변수, 초기값은 첫 번째 요소
        int maxFrequency = 1; // 최대 빈도수를 저장할 변수, 초기값은 1
        int currentFrequency = 1; // 현재 요소의 빈도수를 저장할 변수, 초기값은 1
        boolean isDuplicate = false; // 최빈값이 중복되는지 여부를 저장할 변수

        // 배열을 순회하며 최빈값을 찾음
        for (int i = 1; i < array.length; i++) {
            if (array[i] == array[i - 1]) {
                // 현재 요소가 이전 요소와 같으면
                currentFrequency++; // 현재 요소의 빈도수 증가
            } else {
                // 현재 요소가 이전 요소와 다르면
                currentFrequency = 1; // 현재 요소의 빈도수를 1로 초기화
            }

            if (currentFrequency > maxFrequency) {
                // 현재 빈도수가 최대 빈도수보다 크면
                mostFrequentValue = array[i]; // 최빈값 갱신
                maxFrequency = currentFrequency; // 최대 빈도수 갱신
                isDuplicate = false; // 중복 여부 초기화
            } else if (currentFrequency == maxFrequency) {
                // 현재 빈도수가 최대 빈도수와 같으면
                isDuplicate = true; // 중복 플래그 설정
            }
        }

        // 최빈값이 중복되면 -1을 반환
        if (isDuplicate) {
            return -1;
        }

        return mostFrequentValue; // 최빈값 반환
    }
}

그리고 Map을 사용했을 때,

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int[] array) {
        // 빈도수를 저장할 Map
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        // 배열 요소의 빈도를 계산하여 Map에 저장
        for (int num : array) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            // `getOrDefault` 메서드를 사용하여 키가 존재하면 해당 값을 반환하고,
            // 존재하지 않으면 기본값(여기서는 0)을 반환합니다.
            // 그런 다음, 현재 값을 1 증가시켜 다시 Map에 저장합니다.
        }

        // 최빈값을 찾기 위한 변수들
        int mostFrequentValue = array[0]; // 최빈값을 저장할 변수, 초기값은 첫 번째 요소
        int maxFrequency = 0; // 최대 빈도수를 저장할 변수
        boolean isDuplicate = false; // 최빈값이 중복되는지 여부를 저장할 변수

        // Map을 순회하며 최빈값을 찾음
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            int value = entry.getKey(); // 현재 키
            int frequency = entry.getValue(); // 현재 키의 빈도수

            if (frequency > maxFrequency) {
                // 현재 빈도수가 최대 빈도수보다 크면
                mostFrequentValue = value; // 최빈값 갱신
                maxFrequency = frequency; // 최대 빈도수 갱신
                isDuplicate = false; // 중복 여부 초기화
            } else if (frequency == maxFrequency) {
                // 현재 빈도수가 최대 빈도수와 같으면
                isDuplicate = true; // 중복 플래그 설정
            }
        }

        // 최빈값이 중복되면 -1을 반환
        if (isDuplicate) {
            return -1;
        }

        return mostFrequentValue; // 최빈값 반환
    }
}

if, for은 좀 이해가 되는데 map은 아예 모르겠다. 다른 사람들 풀이를 살펴보니까 진짜 정신나간 코드도 있었다.

import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public int solution(int[] array) {
        List<Map.Entry<Integer, List<Integer>>> list = new ArrayList<>(Arrays.stream(array).boxed().collect(Collectors.groupingBy(o -> o)).entrySet()).stream().sorted((t0, t1) -> Integer.compare(t1.getValue().size(), t0.getValue().size())).collect(Collectors.toList());
        return list.size() > 1 && list.get(0).getValue().size() - list.get(1).getValue().size() == 0 ? -1 : list.get(0).getKey();
    }
}

이게 뭔가,,, ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이걸 한줄로도 풀 수 있네? 진짜 코딩은 무궁무진한가보다.

일단 오늘은 여기까지 나중에 집 가서 코드 한번 더 찬찬히 살펴봐야겠다.