HashMap [자료구조] (프로그래머스 - 최빈값 구하기)

프로그래머스 - 최빈값 구하기 

1. 1000개의 숫자의 빈도수를 저장하기위해 1000 길이를 갖는 배열을 만들어서 인덱스에 빈도수를 저장하는 방식으로 풀었다.

2. 가장 큰 빈도수가 중복되면 안되기에 처음에 제일큰 빈도수와 해당 숫자를 구하고

3. 그 빈도수를 -1로 지정하고 그 다음으로 큰 빈도수를 구했다.

class Solution {
    public int[] idxnum;
    public int solution(int[] array) {
        int answer = 0;
        idxnum = new int[1000];
        for(int a : array){
            idxnum[a]++;
        }
        int max1cnt = 0;
        int max1num = 0;
        int max2cnt = 0;
        int max2num = 0;
        for(int i=0;i<idxnum.length;i++){
            if(idxnum[i]>max1cnt){
                max1cnt = Math.max(max1cnt,idxnum[i]);
                max1num = i;
            }
        }
        idxnum[max1num]-=1;
        for(int i=0;i<idxnum.length;i++){
            if(idxnum[i]>max2cnt){
                max2cnt = Math.max(max2cnt,idxnum[i]);
                max2num = i;
            }
        }
        if(max1cnt==max2cnt){
            answer = -1;
        }else{
            answer = max1num;
        }
        
        
        return answer;
    }
}

하지만 푸는 내내 키와 값을 저장할 수 있는 Map을 이용해서 고유한 숫자와 그 빈도수를 저장하며 풀면 좋을것 같다는 생각을 했고 아직 Map 개념이 잘 잡혀있지 않아서 공부를 해보기로 했다.

 

---

---

HashMap

 

HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션

Map 인터페이스를 상속하고 있기에 Map의 성질을 그대로 가지고 있다.

(Map은 키와 값으로 구성된 Entry객체를 저장하는 구조를 가지고 있는 자료구조)

• 여기서 키와 값은 모두 객체. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없음.
• 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다.

HashMap은 이름 그대로 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다.

HashMap은 해시 함수를 통해 '키'와 '값'이 저장되는 위치를 결정하므로,

사용자는 그 위치를 알 수 없고, 삽입되는 순서와 들어 있는 위치 또한 관계가 없습니다. 

아하!! 해쉬맵을 사용하면 삽입순서와 상관없이 위치가 결정되기에 순서로 불러올수는 없나보다!

그렇다면 해쉬맵을 어떻게 사용해야할까?

 

HashMap 사용법

선언

HashMap<String,String> map1 = new HashMap<String,String>();//HashMap생성
HashMap<String,String> map2 = new HashMap<>();//new에서 타입 파라미터 생략가능
HashMap<String,String> map3 = new HashMap<>(map1);//map1의 모든 값을 가진 HashMap생성
HashMap<String,String> map4 = new HashMap<>(10);//초기 용량(capacity)지정
HashMap<String,String> map5 = new HashMap<>(10, 0.7f);//초기 capacity,load factor지정
HashMap<String,String> map6 = new HashMap<String,String>(){{//초기값 지정
    put("a","b");
}};

 

HashMap을 생성하려면 키 타입과 값 타입을 파라미터로 주고 기본생성자를 호출하면 된다.

HashMap은 저장공간보다 값이 추가로 들어오면 List처럼 저장공간을 추가로 늘리는데

List처럼 저장공간을 한 칸씩 늘리지 않고 약 두배로 늘립니다.여기서 과부하가 많이 발생한다

그렇기에 초기에 저장할 데이터 개수를 알고 있다면 Map의 초기 용량을 지정해주는 것이 좋다!

 

HashMap 값 추가

HashMap<Integer,String> map = new HashMap<>();//new에서 타입 파라미터 생략가능
map.put(1,"사과"); //값 추가
map.put(2,"바나나");
map.put(3,"포도");

 

HashMap에 값을 추가하려면 put(key,value) 메소드를 사용하면 된다.

선언 시 HashMap에 설정해준 타입과 같은 타입의 Key와 Value값을 넣어야 하며 만약 입력되는 키 값이 HashMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로 대치된다..

HashMap 값 삭제

HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"사과");
    put(2,"바나나");
    put(3,"포도");
}};
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

 

HashMap에 값을 제거하려면 remove(key) 메소드를 사용하면 된다.

오직 키값으로만 Map의 요소를 삭제할 수 있다.

모든 값을 제거하려면 clear() 메소드를 사용하면 됩니다.

HashMap 값 출력

HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"사과");
    put(2,"바나나");
    put(3,"포도");
}};
		
System.out.println(map); //전체 출력 : {1=사과, 2=바나나, 3=포도}
System.out.println(map.get(1));//key값 1의 value얻기 : 사과
		
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

 

HashMap을 출력하는 방법에는 다양한 방법이 있다.

1. 그냥 print하게 되면 {}로 묶어 Map의 전체 key값, value가 출력된다.
2. 특정 key값의 value를 가져오고싶다면 get(key)를 사용하면 된다.
3. 전체를 출력하려면 entrySet()이나 keySet()메소드를 활용하여 Map의 객체를 반환받은 후 출력하면 된다.

entrySet()은 key와 value 모두가 필요할 경우 사용한다.

keySet()은 key 값만 필요할 경우 사용한다.

 

key값만 받아서 get(key)를 활용하여 value도 출력할 수도 있기에 어떤 메소드를 선택하든지 간에 큰 상관이 없어 대부분 코드가 간단한 keySet을 활용하시던데 key값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되므로 많은 양의 데이터를 가져와야 한다면 entrySet()이 좋습니다.(약 20%~200% 성능 저하가 있음)

아하! 많은 양의 데이터를 가져올 때는 성능을 생각해서는 entrySet()을 사용하는 쪽으로 생각해야겠다.

 

Iterator 사용

 

HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"사과");
    put(2,"바나나");
    put(3,"포도");
}};
		
//entrySet().iterator()
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" +  entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도
		
//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

 

HashMap의 전체출력 시 반복문을 사용하지 않고 Iterator를 사용하여도 된다.

 

출처  : https://coding-factory.tistory.com/556

key 존재여부

        // HashMap 준비
        Map<Integer, String> map = new HashMap<Integer, String>();
        map.put(1, "Apple");
        map.put(2, "Banana");
        map.put(3, "Orange");
        map.put(null, "Tomato");
 
        // 특정 key값 존재여부 체크 (containsKey())
        System.out.println(map.containsKey(1));   // true
        System.out.println(map.containsKey(5));   // false
        System.out.println(map.containsKey(null));   // true

 

map이름.containsKey()

그렇다면 key의 존재여부는 어떻게 알 수 있을까 boolean containsKey​(Object key)를 통해 알 수 있다.

---

---

자 이제 다시 최빈값 구하기를 풀어보자 이번에 HashMap을 이용해서 푸는 것이다.

 

 

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

class Solution {
    public Map<Integer,Integer> map = new HashMap<>();
    public int solution(int[] array) {
        int answer = 0;
        for(int num : array){
            if(map.containsKey(num))
                map.put(num,map.get(num)+1);
            else
                map.put(num,1);
        }
        int maxV = 0;
        int maxK = 0;
        for(Entry<Integer,Integer> entry : map.entrySet()){
            if(maxV<entry.getValue()){
                maxV = entry.getValue();
                maxK = entry.getKey();
            }else if(maxV==entry.getValue()){
                maxK = -1;
            }
        }
        answer = maxK;
        return answer;
    }
}

 

 

아하아하 끝이 아니다.

알면알수록 알게 더 많아지는 그런 상황

 

여기서 내가 key 값이 이미 있으면 value에 1을 더하고 없으면 key,0 값을 넣으려고 한다.

int count = map.getOrDefault(number, 0);

그럴 때는 이렇게 getOrDefault를 사용할 수 있다.

만약 key 값이 없다면 괄호 안의 값으로 초기값을 등록하고 있다면 해당 key의 value를 가져오는 식이다.

 

그리고 꼭 Entry 반복문을 쓸 필요 없이 아래처럼 풀어도 된다.

import java.util.*;
class Solution {
    public int solution(int[] array) {
        int maxCount = 0;
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        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;
    }
}

 

 

오늘도 알차게 공부했다 ㅎㅎ그럼 이만~!!!