[leetcode] Medium-49번. Group Anagrams 문제풀이

문제

https://leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

 

 

 

 

풀이코드

package SITE03_leetcode.medium;

import java.util.*;
import java.util.stream.Collectors;

/**
 * https://leetcode.com/problems/group-anagrams/
 */
public class M023_leetcode49_GroupAnagrams {
    public static void main(String[] args) {
        M023_leetcode49_GroupAnagrams solution = new M023_leetcode49_GroupAnagrams();
        String[] a = new String[]{"", ""};

        System.out.println(solution.groupAnagrams(a));
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();

        if (strs.length == 1) {
            result.add(List.of(strs));
            return result;
        }

        Map<String, String> map = new HashMap<>();
        for (String target : strs) {
            if ("".equals(target)) {
                target = " ";
            }

            // key : 사전순
            String key = getKey(target);
            if (!map.containsKey(key)) {
                map.put(key, target);
            } else {
                map.put(key, map.get(key) + "," + target);
            }
        }

        // 꺼내기
        for (Map.Entry<String, String> entry : map.entrySet()) {
            // "," 구분자로 배열 변환
            String[] targetArr = entry.getValue().split(",");
            Arrays.sort(targetArr);

            // array to List (trim : 공백의 경우 위에서 넣어줬기 때문)
            List<String> list = Arrays.stream(targetArr).map(String::trim).collect(Collectors.toList());
            result.add(list);
        }

        return result;
    }

    public String getKey(String target) {
        char[] charArr = target.toCharArray(); // String to Char Array
        Arrays.sort(charArr); // Char Array 알파벳 순 정렬

        return String.valueOf(charArr);
    }
}

 

 

 

 

Discuss

위 풀이코드도 정답이나, 시간이 54 ms가 걸린다. 좀더 나은 다른 정답 코드를 보자.

 

출처 : https://leetcode.com/problems/group-anagrams/discuss/19350/7-lines-java-solution

package SITE03_leetcode.medium;

import java.util.*;
import java.util.stream.Collectors;

/**
 * https://leetcode.com/problems/group-anagrams/
 */
public class M023_leetcode49_GroupAnagrams {
    public static void main(String[] args) {
        M023_leetcode49_GroupAnagrams solution = new M023_leetcode49_GroupAnagrams();
        String[] a = new String[]{"", ""};

        System.out.println(solution.groupAnagrams(a));
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            /* 배열 변환 후 정렬 */
            char[] chars = str.toCharArray();
            Arrays.sort(chars);

            /* key 추출 (사전순) */
            String key = String.valueOf(chars);

            /* computeIfAbsent() 메서드를 사용하여 key가 존재 유무에 따라 설정 */
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        
        return new ArrayList<>(map.values());
    }
}

 

코드가 훨씬 간결하다. 해당 코드의 풀이 프로세스는 위의 내가 풀이한 코드와 동일하다. 사전순으로 정렬한 문자열을 key로 두고, 해당 key의 존재 유무에 따라 리스트에 추가하는 방식이다. computeIfAbsent() 메서드를 사용하여 좀더 간결하게 해결할 수 있는 문제였다.

 

computeIfAbsent()

...
    default V computeIfAbsent(K key,
            Function<? super K, ? extends V> mappingFunction) {
        Objects.requireNonNull(mappingFunction);
        V v;
        if ((v = get(key)) == null) {
            V newValue;
            if ((newValue = mappingFunction.apply(key)) != null) {
                put(key, newValue);
                return newValue;
            }
        }

        return v;
    }
...

 

computeIfAbsent 메서드가 받는 mappingFunction 람다식은 key가 존재하지 않을때만 수행된다. 따라서 key가 존재하지 않을때 새로운 리스트가 생성되고, 리턴되는 Value 에 데이터가 add 되는 형식이다.

 

참고 포스팅

https://devfunny.tistory.com/465

[Java8] Map의 key 가 null 일 경우 처리 방법