Algorithm 7

2cong·2020년 6월 27일
0

Algorithm

목록 보기
5/6

1. 처음 풀이 --> 틀린 풀이

def groupAnagrams(strs):
    a_list = []
    my_dict = {}
    
    for i in strs:
        # set을 이용하여서 알파벳 중복을 체크함
        # 중복된 값이 없는 경우
        if set(i) not in a_list :
            # list에 추가
            a_list.append(set(i))
            nums=a_list.index(set(i))
            # list에 추가된 index값을 이용하여 딕셔너리 생성
            my_dict[nums]=[i]
            
        # 중복된 값이 없는 경우
        elif set(i) in a_list:
            # 딕셔너리에 값 추가
            nums=a_list.index(set(i))
            my_dict[nums].append(i)
        
    return my_dict.values()

문제점

set 으로 판단하니 같은 글자가 반복되는 경우 같은 값으로 판단하게 됨

ex) boo, bob의 경우
위의 경우 문자의 구성이 다른데, {'b', 'o'}로 같은 set값을 가지게 됨
따라서 set으로 알파벳 구성의 중복 체크는 사용 불가

2. 고친 풀이

위의 풀이에서는 중복 체크를 set을 이용하여 함
고친 풀이에서는 sorted를 이용하여 중복 체크를 함

def groupAnagrams(strs):
    a_list = []
    my_dict = {}
    
    for i in strs:
        # sorted를 이용하여 알파벳 구성의 중복 체크 
        # 중복된 값이 있는 경우
        if sorted(i) not in a_list:
            # list에 추가
            a_list.append(sorted(i))
            nums=a_list.index(sorted(i))
            # 딕셔너리에 값 추가
            my_dict[nums]=[i]
        
        # 중복된 값이 없는 경우
        elif sorted(i) in a_list:
            # 딕셔너리에 값 추가
            nums=a_list.index(sorted(i))
            my_dict[nums].append(i)
	
    return my_dict.values()

풀이 방법

sorted를 이용하여 알파벳의 순서를 변경
ex) nat, tan --> 모두 ['a', 'n', 't'] 가 됨

위의 변경된 알파벳을 리스트에 추가하고 리스트에 값이 있는지 없는지로 알파벳 순서쌍의 중복을 체크함

이 값들을 모아서 출력하기 위하여 딕셔너리 사용
리스트의 인덱스를 key로 두고 value를 list로
ex) my_dict = {0:['bat'] , 1:['nat','tan']} ... 와 같은 형식으로 만들어 줌

3. 다른 풀이

def groupAnagrams(strs):
    d = {}
    
    for w in sorted(strs):
        key = tuple(sorted(w))
        d[key] = d.get(key, []) + [w]
        print(d)
    return d.values()

풀이 방법

sorted 한 결과를 tuple로 저장해서 이 값을 딕셔너리의 key로 사용
딕셔너리의 value에 list 값을 더하는 형식!

0개의 댓글