[BEAKJOON] 백준 6566 - 애너그램 그룹

 

 

https://www.acmicpc.net/problem/6566

6566번: 애너그램 그룹

 

 

처음에 해당 문제를 SET 집합을 사용하여 합집합이고 같은 것을 묶어야 하나 생각을 했었는데,

그러면 중복되는 값이 없어지게 되기 때문에 정보의 손실이 일어나니

틀린 값이 나올 확률이 있다.

 

그러면 해당 문자열들의 각 문자 값들을 어떻게 같은건지 확인을 할 수 있을까? 하면

abc 알파벳 순서대로 정렬을 해주는 것을 생각할 수 있다.

 

주의할점 

1. "같은 단어는 한번만 출력", 예를들어서 입력으로 "a"가 5번이나 들어왔다면, 출력은 "Group of size 5 : a"와 같이 이루어져야 한다.

---

Collections 모듈

Collections.defaultdict

 

1. defaultdict 란

collections.defaultdict은 딕셔너리와 거의 비슷하지만, key 값이 없을 경우 미리 지정해 놓은 초기 (default) 값을 반환하는 dictionary이다. 

 

사전에 기본값을 설정해줘야 할 때는 파이썬 내장 모듈인 collections의 defaultdict 클래스를 사용하면 좋다.

defaultdict 클래스의 생성자로 기본값을 생성해 주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값을 설정해준다.

---

* sort () : 원본에 직접 정렬하는 함수

* sorted () : 새로운 리스트를 생성하여 정렬

 

그러면 해당 키 값을 정렬된 sorted() 함수를 사용하여 정렬하여 키값으로 만들고,

해당 기존의 word를 add 해준다.

 

그래서 해주면 아래처럼 값이 저장된다.

defaultdict(<class 'list'>, {'addeilnpsuy': ['undisplayed'], 'acert': ['trace', 'crate', 'cater', 'carte', 'caret'], 'aet': ['tea', 'eta', 'eat', 'ate'], 'egilnnost': ['singleton'], 'addeilpsy': ['displayed'], 'abet': ['beta', 'beat', 'bate', 'abet']})

 

 

이제 남은건 

"단어는 사전순으로" 는 아래와 같이 새로운 딕셔너리 형태로 정의한다.

key 값은 그대로, value 값은 sorted 되게 만들어서 저장한다.

해당 key 와 value의 값은 anagrams의 items에서 가져온 것이다.

{key: sorted(value) for key, value in anagrams.items()}

 

 

"단어 카운트" 는 아래와 같이 해당 k에 따른 anagrams의 value값의 크기를 측정해주었습니다.

시간 복잡도면으로도 낫뱃

{k: [sorted(v), len(anagrams[k])] for k, v in anagrams.items()}

 

 

"중복된 단어 제거" 를 해줘야 한다.

간단하게 집합으로 중복된 단어를 제거해주면 된다고 생각했다.

{k: [set(sorted(v)), len(anagrams[k])] for k, v in anagrams.items()}

인데~ set이랑 sorted랑 자리를 바꿔줘야 한다!

{k: [sorted(set(v)), len(anagrams[k])] for k, v in anagrams.items()}

 

그리고 "순서대로 만들어주기"

lambda 함수는 각 아이템을 받아 정렬의 기준으로 사용할 값을 반환하는데,

item[1][1]는 각 아이템의 두번째 요소, 해당 key에 따른 value의 값을 저장해둔 값을 정렬하는 것인데,

"-" 기호는 내림차순으로 정렬한다는 의미이다.

 

여기까지하면, 갯수 순서대로 순서가 맞춰지는데, 뒤에 더 추가한 이유가

같은 크기일 때, 사전순으로 단어의 순서를 바꾸기 위해서이다.

그래서 맨 처음의 단어(이미 해당 단어 리스트 내에서 사전 순으로 정렬을 했기 때문에, 맨 앞의 단어가 사전순으로 제일 빠른 단어임) 를 의미하는 sorted(item[1][0])의 [0]는 첫번째 단어라는 것이다. 같은 크기의 그룹을 비교할 때 사용되었다.

sorted_anagrams = sorted(filtered_anagrams.items(), key=lambda item: (-item[1][1], sorted(item[1][0])[0]))

 

---

sorted 함수

sorted 함수는 key를 인자로 정해서 할 수 있는데,

key 인자에 함수(lambda, 람다)를 넘겨주면 우선순위가 정해진다.

 

lambda 매개변수 : 표현식

 

lambda x : x[0] => 이런 식으로 사용하는데,

- 를 붙이면 리버스가 됨

 

---

 

이제 마지막으로 출력만 해주면 된다!

출력은 어쩔 수 없이 n의 시간 복잡도로 for문과 같은 반복문으로 진행한다.

 

    print(f'Group of size {sorted_anagrams[i][1][1]}: {" ".join(sorted_anagrams[i][1][0])} .')

 

 

최종 코드는 아래와 같다.

import collections

anagrams = collections.defaultdict(list)

while(True):

    try:

        word = input()

        anagrams["".join(sorted(word))].append(word)

    except EOFError:

        break

filtered_anagrams = {k: [sorted(set(v)), len(anagrams[k])] for k, v in anagrams.items()}

sorted_anagrams = sorted(filtered_anagrams.items(), key=lambda item: (-item[1][1], sorted(item[1][0])[0]))

for i in range(0, 5):

    print(f'Group of size {sorted_anagrams[i][1][1]}: {" ".join(sorted_anagrams[i][1][0])} .')

'''

undisplayed

trace

tea

singleton

eta

eat

displayed

crate

cater

carte

caret

beta

beat

bate

ate

abet

'''

 

 

 

역시 재미있다 ^.^