[PCCP] 문자열과 해시함수 [4]

▼ Why ?

이전 문제처럼 입력받은 문자열에서 문자들의 빈도수를 다루는 문제여서 먼저 풀어보려고 한다.

---

▼ 자기 분열수

 

문제 정보

• 자기 분열수란 배열의 원소 중 자기 자신의 숫자만큼 빈도수를 갖는 숫자를 의미합니다.
• 만약 배열이 [1, 2, 3, 1, 3, 3, 2, 4] 라면 1의 빈도수는 2, 2의 빈도수는 2, 3의 빈도수는 3, 4의 빈도수는 1입니다.
  여기서 자기 자신의 숫자와 같은 빈도수를 갖는 자기 분열수는 2와 3입니다.
• 매개변수 nums에 자연수가 원소인 배열이 주어지면 이 배열에서 자기 분열수 중 가장 작은 수를 찾아 반환하는 프로그램을 작성하세요.
• 자기 분열수가 존재하지 않으면 -1를 반환하세요.

 

입출력 예

 

제한사항

• nums의 길이 3 <= n <= 500,000
• 배열 nums의 원소는 자연수입니다. 1 <= nums[i] <= 1,000,000

 

어떻게 해결해야 할까?

1. 일단 key(숫자)-value(빈도수)를 쌍으로 하는 HashMap class의 instance(' numFreq ')를 생성하여 값을 저장한다
2. 자기 분열수 중 가장 작은 값을 반환해야 하기 때문에, 반환할 값을 담을 int형 변수(' min ')를 하나 생성한다
3. 그리고 자기 분열수를 찾을 때마다 하나의 배열에 담고, 해당 배열을 오름차순 정렬(' sort() ')을 시켜 첫 번째 index에 있는 값을 반환하는 방법도 있겠지만, 굳이 배열을 만들어 정렬까지 시킬 필요는 없을 것 같아 ' min ' 을 이용하기로 했다
4. ' numFreq ' 에서 key와 value의 값이 일치하고(자기 분열수) 해당 key 값이 ' min ' 담긴 값보다 작으면, ' min ' 에 해당 key의 값이 저장되도록 하자
   ( 배열 nums의 원소(element)는 1,000,001보다 작은 자연수이기 때문에, ' min ' 을 1,000,001로 초기화해준다 )
5. 자기 분열수가 없다면 '-1'을 반환해야 하기 때문에, ' min ' 의 값이 초기값 그대로일 경우 '-1'을 반환하도록 한다

 

해결 코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        HashMap<Integer, Integer> numFreq = new HashMap<>();
        
        for(int num : nums) {
            numFreq.put(num, numFreq.getOrDefault(num, 0) + 1);
        }
        
        int min = 1000001;
        
        for(int key : numFreq.keySet()) {
            if(key == numFreq.get(key) && key < min) {
                min = key;
            }
        }
        
        return min == 1000001 ? -1 : min;
    }
}

 

---

▼ 정리

 

• ' getOrDefault(Object key, V DefaultValue) ' 메서드의 매개변수 순서를 헷갈리지 않도록 조심하자
  
  
• 이 문제를 해결한 방법 말고 ' Arrays.sort() ' 나 ' Collection.sort() ' 같은 메서드로 정렬하는 방식으로도 풀 수 있지만, 사실 정렬하지 않고 위 방법처럼 해결하든 정렬해서 해결하든 시간복잡도는 O(n)으로 차이가 없다
  
  
• 추가적으로, ' Arrays.sort() ' 와 ' Collection.sort() ' 는 어떤 차이가 있는지 한 번 공부해보는 것이 좋을 것 같다