Part 03 Map

1. Map

  -  Map은 array와 list의 장점만 모아놓았다.

 

  Def) hashing

  - key를 범위(배열 크기)에 맞게 적절이 겹치지 않는 index로 변경한다.

 

  Ex)

<hide/>
import java.util.Hashtable;
public interface MapP {
	public static void main(String[] args) {
		
        Hashtable<String, Integer> map = new Hashtable<>();
		map.put("A", 1);
		map.put("B", 2);
		map.replace("A", 11);
		
		System.out.println(map.remove("B", 3));  	// map에 B,2가 있으면 삭제된다.
		System.out.println(map);
		System.out.println(map.get("A"));
		System.out.println(map.getOrDefault( "C",  -1));
		System.out.println(map.keySet());	// key만 출력
		System.out.println(map.values()); 	// value만 출력
	}
}

  Note) 실행 결과

  - Map interface를 상속하는 클래스가 여러 개 있는데 hashmap과 hashtable이 자주 쓰인다.

 

   

  Ex)  Map 이용 방법

<hide/>
package first;
import java.util.Hashtable;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ConcurrentHashMap;


class MyData{
	
	int value;
    
	public MyData(int value) {
		this.value = value;
	}
	
	static MyData create(int v) {
		return new MyData(v);
	}	
	
    @Override
	public String toString() {
		return "[" + value + "]";
	}
    
    @Override
	public boolean equals(Object o) {
		if(this == o)	return true;
		if(o == null || getClass() != o.getClass())	return false;
		MyData mydata = (MyData) o;
		return value == mydata.value;
	}
    
    @Override
	public int hashCode() {
		return Objects.hash(value);		
		// 같은 value가 들어가면 같은 해시값이 나온다.
		// 키로 사용되는 것은 해시코드를 호출해서 나온 해시값을 이용해서 인덱스로 이용한다.
	}
	
}

public class Main {

	public static void main(String[] args) {
		
		 Map<MyData, Integer> map = new ConcurrentHashMap<>();	// <key: String , value: Integer>
			map.put(new MyData(1), 1);
			map.put(new MyData(2), 2);
			map.replace(new MyData(1), 1, 11);
			method1(map);
			
	}
			static void method1(Map<MyData, Integer> map) {
				
				System.out.println(map.remove(new MyData(2), 2));  
				System.out.println(map);
				System.out.println(map.get(new MyData(1)));
				System.out.println(map.getOrDefault(new MyData(3), -1));	// map에 C가 없으면 대신 -1반환
				System.out.println(map.keySet());	// key만 출력
				System.out.println(map.values()); 	// value만 출력
			}
}

  Note) 실행 결과

 

 

 

 

  Ex) 포켓몬

  - 배열의 N마리 포켓몬 중에서 최대 N / 2 만큼 가져갈 수 있다.

  - 이 때 포켓몬 종류수의 최댓값 구하기

  - keySet을 통해 포켓몬의 종류의 개수를 구한다.

<hide/>
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n : nums){
            map.put(n, 0);      // 포켓몬의 종류를 구한다.
        }
        
        int n1 = map.keySet().size();  // keyset의 사이즈를 구하면 포켓몬 종류의 개수 구할수있음
        int n2 = nums.length / 2;   // 배열 크기의 절반을 구한다.

        return Math.min(n1, n2);
    }
}

 

  Ex) 완주하지 못한 선수 (Map)

  - 마라톤 참가자(participant)와 완주자(completion) 배열이 주어졌을 때, 완주하지 못한 선수의 이름을 리턴

  - completion의 길이는 participant보다 1 작다.

<hide/>
import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        
        // 전제시간복잡도: O(n)
        Map<String, Integer> players = new HashMap<>();  // String: 선수이름, Integer: 카운트
        
        // O(n)
        for(String p : participant){
            players.put(p, players.getOrDefault(p, 0) + 1);	// 선수들 명단을 만든다.
        }
        
        // O(n)
         for(String c : completion){ 
             int n = players.get(c) - 1;			// 완주자 명단을 확인한다.
             if(n == 0) players.remove(c);			// 이름이 더이상 없으면 선수 이름을 제거
             else players.put(c, n);				//  n이 0이 아니면 다시 그 값을 갱신한다.
         }     
        // O(1) 
        return players.KeySet().iterator().next();	
        // iterator를 통해 한 명의 이름을 꺼내온다.
        // 최종적으로 한 명 밖에 안 남는다.
    }
}

  - getODefault( Key, value ): 지정된 키로 매핑된 값이 없는 경우 반환되는 기본값

    -> 키가 존재하면 키 값을 반환,  없으면 0반환, 거기에 +1 

  - for문을 통해 이름, +1을 넣어준다.

  - n이 0이 아니면 다시 n값을 갱신해서 넣어준다.

  - else문은 없어도 실행된다.

  - 배열로 풀때보다 Map으로 풀 때의 시간 복잡도가 낮고 효율적이다.

 

  Ex) 완주하지 못한 선수 (배열)

<hide/>
    // 전체 시간 복잡도: O(nlogn)
    Arrays.sort(participant); // n명   // O(nlogn)
    Arrays.sort(completion); // n-1명  // O(nlogn)
    
	// O(n)
    for(int i = 0; i < completion.length; ++i){
        if( !participant[i].equals(completion[i])) return participant[i];
      
    }
    return participant[participant.length - 1];

 

  Ex) 위장 문제

<hide/>
import java.util.*;
class solution {
	public int solution(String[][] clothes){
    	Map<String, Integer> map = new HashMap<>();
        
        // 위장용품의 종류별 개수를 구한다
        for(String[] c : clothes){
        	String type = c[1];
        	map.put(type, map.getOrDefault(type, 0) + 1);
        }
        
        // 각 개수의 +1을 모두 곱한다.
        int answer = 1;
        var iter = map.values().iterator();
        // var는 타입을 생략, 컴파일러가 추론한다.
        // 개수
        
        while(iter.hasNext()){
        	answer *= iter.next() + 1;
        }
        // -1해서 리턴한다. (착용하지 않는 경우도 생각한다. )
        return answer - 1; 
    }
}

 

  - map을 구하면 개수를 구하기 편하다.

  - var iter = map.values().iterator();
    -> var: 타입을 정하지 않고 iter라는 변수를 선언한다.
    -> map.values(): map의 value들을 가져온다.        
    -> map.values().iterator(): 위에서 반환되는 모든value를 iter에 저장한다.
  - while(iter.hasNext())   { answer *= iter.next() + 1; }
    -> iter.hasNext(): iter안에 값이 계속 있다면 반복, iter 안에 더 요소가 있는지 확인
    -> iter.next(): 뒤에 있는 값

 

 

 

 

 

 

 

출처: https://programmers.co.kr/learn/courses/13577/lessons/96083