알고리즘에서 쓰일 수 있는 MAP을 활용 예제

구현 문제들을 풀다보니, 실버3부터는 MAP을 활용해야 하는 경우가 많이 생겼다. stack이나 queue는 예전에도 자주 썼기 때문에 낯설지 않지만, map의 경우는 메모리를 많이 잡아먹다보니 안썼던 것 같다.

---

중복 갯수 세기

getOrDefalut(key,default value) 메소드 사용 = 찾는 키가 존재한다면 값을 반환(없을 경우 default value 값을 반환)

Map<String, Integer> map = new HashMap<>();
        String s[] = {"aa" , "bb" , "cc" , "aa"};

        for(String i:s){
            map.put(i, map.getOrDefault(i,0)+1);
        }
        System.out.print(map);

실행결과 : {aa=2, bb=1, cc=1}

map에 s를 순회하며 키를 넣을 때, 없다면 기본값인 0에 증가값인 1을 더해준다. 있다면 그냥 +1을 해줌.

---

MAP 순회

단일 key 값만 순회

for(String i:map.keySet()){
            System.out.print(i);
   }

단일 value 값만 순회

for(Integer i:map.values()){
            System.out.print(i);
   }

key, value 둘 다 순회할 때

for(Map.Entry<String, Integer> entry:map.entrySet()){
            System.out.println(entry.getKey() + " " + entry.getValue());
 }

---

MAP 정렬

정렬을 위해서는 list에 담아서 하는 것이 좋다.

key를 정렬

Map<String, Integer> map = new HashMap<>();
        String s[] = {"aa" , "bb" , "cc" , "dd" , "ba", "bc"};

        int cnt = 0;
        for(String i:s){
            map.put(i,cnt++);
        }
        List<String> list = new LinkedList<>();
        for(String i:map.keySet()){
            list.add(i);
        }
        Collections.sort(list);
        for(String i:list){
            System.out.println(i);
        }

내림차순의 경우 Collections.sort(list,Collections.reverseOrder())를 사용한다.

value를 정렬(오버라이딩을 통해 sort의 compare를 키 값에 대한 벨류 값의 비교로 만든다.)

Map<String, Integer> map = new HashMap<>();
        String s[] = {"aa" , "bb" , "cc" , "dd" , "ba", "bc"};

        int cnt = 0;
        for(String i:s){
            map.put(i,cnt++);
        }
        List<String> list = new LinkedList<>(map.keySet());

        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return map.get(a).compareTo(map.get(b));
            }
        });
        for(String a:list){
            System.out.println(a + " " + map.get(a));
        }

compare을 통해서 map의 value를 비교 해본 뒤 정렬한다. 역순으로 정렬하기 위해서는 return map.get(b).compareTo(map.get(a)); 를 사용.