[leetcode] 49. Group Anagrams 풀이, 해설 (python)

 

문제 링크 

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

Group Anagrams - LeetCode

 

'eat','aet','tae' 등으로 동일한 캐릭터로 순서만 바꿔서 나왔을때, 

해당 문자열들을 리스트로 모아서 뿌려주는 문제이다. 

 

내가 먼저 생각했던 거는 e1a1t1 등으로 각각 문자와 카운트를 나열한다음에 이거를 키로 해서 해시맵을 만들어서 가면 될 거 같다고 생각했는데,

구현하는 과정에서 a1e1t1과 a1t1e1 을 같은 key로 설정하는 과정에서 애를 먹어서 다른 방법으로 시도하기로 했다. 

 

1차 풀이

1. 먼저 strs를 돌면서 알파벳을 정렬해서 새로운 배열 sortedStrs에 저장한다. (eat -> aet, tae -> aet)

2. sortStrs를 다시 정렬한다. 그러면 동일한 것끼리 묶을 수 있게 된다. 

3. sortedStr를 돌면서, 결과값 results의 마지막 값과 현재 값이 일치하면 그 전에 넣어주고 아니면 새로운 배열에 넣어준다. 

# 1. 먼저 strs를 돌면서 알파벳을 정렬해서 새로운 배열 sortedStrs에 저장한다. (eat -> aet, tae -> aet)
sortedStrs = []
for str in strs:
    # 돌면서 eat -> aet 알파벳순으로 정렬 
    sortedStrs.append((str, ''.join(sorted(str))))


# 2. sortStrs를 다시 정렬한다. 그러면 동일한 것끼리 묶을 수 있게 된다. 
sortedStrs.sort(key = lambda x:x[1])


# 3. sortedStr를 돌면서, 결과값 results의 마지막 값과 현재 값이 일치하면 그 전에 넣어주고 아니면 새로운 배열에 넣어준다. 
results = [[sortedStrs[0][0]]]
# 동일한 것끼리 묶어주기 
for i in range(1, len(sortedStrs)):
    originalValue = sortedStrs[i][0]
    checkValue = sortedStrs[i][1]

    # 전에 값과 동일하다면, 전 배열에 넣어주고 
    if sortedStrs[i - 1][1] == checkValue:
        results[-1].append(originalValue)
    # 전에 값과 다르면, 새로운 배열에 추가 
    else:
        results.append([originalValue])

마지막 3번 과정이 복잡하긴 한데, 지금와서 생각해보면 defaultdict를 이용해서 쉽게 접근할 수 있지 않았나 싶다. 

 

2차 풀이 (해설 참고)

해설 유투브는 아래 링크를 참고했다. 

https://www.youtube.com/watch?v=vzdNOK2oB2E 

49. Group Anagrams 해설 링크

일단 접근 방식 자체는 첫번째 생각했던 방식과 유사했다. 

내가 생각하지 못했던 것은 1. list를 tuple로 바꿔서 dictionary의 key로 사용할 수 있다는 것. 2. 알파벳의 갯수 count 시 [0] * 26 배열을 사용할 수 있다는 것이었다. 

 

풀이는 다음과 같다. 

1. 먼저 strs를 돌면서 count 배열에 알파벳 수를 각각 카운트 한다. 

이때, count 배열의 0,1,2,...26은 알파벳 a,....z에 해당할 수 있도록 ord라는 아스키배열 값을 가져오는 함수를 쓴다. 

2. 그 다음 count배열을 tuple로 바꿔 results 배열의 key로 사용해 저장한다. 

3. results 를 리턴한다. 

 

# 리스트를 값으로 갖는 딕셔너리를 생성하면, 딕셔너리에 키를 추가할 때 키가 존재하지 않으면 빈 리스트가 자동으로 생성
results = defaultdict(list)

# 1. 먼저 strs를 돌면서 count 배열에 알파벳 수를 각각 카운트 한다. 
## 이때, count 배열의 0,1,2,...26은 알파벳 a,....z에 해당할 수 있도록 ord라는 아스키배열 값을 가져오는 함수를 쓴다. 

for s in strs:
    count = [0] * 26          # 알파벳 만큼 만들기 
    for c in s:
        # 아스키 코드에서 'a'는 97이고, 'b'는 98, 'c'는 99, 이런 식으로 계속 증가
        count[ord(c) - ord('a')] += 1 

	
	2. 그 다음 count배열을 tuple로 바꿔 results 배열의 key로 사용해 저장한다. 
    # count 를 tuple 형태로 바꿔야 'unhashable type:list 안 발생함 '
    results[tuple(count)].append(s)


# 3. results를 출력한다. 
return results.values()

 

훨씬 코드가 간결해졌다 !! 

 

참고로, 이 방식을 java에서도 사용가능한지 궁금해서 chatgpt에게 물어봤는데,

역시 똑똑한 chatgpt

 

아래와 같이 array를 string으로 바꿔서 key로 사용하면 된다고 한다. 

String key = Arrays.toString(count);

 

chatgpt가 제공해준 코드는 아래와 같다. 

public static List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();

    for (String s : strs) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }

        // 배열을 문자열로 변환하여 키로 사용
        String key = Arrays.toString(count);

        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(s);
    }

    return new ArrayList<>(map.values());
}

 

 

참고해보면 좋을 링크 

https://ddoance.tistory.com/139

알고리즘 풀이순서. neetcode 참고해서 leetcode 준비하기 (leethub)