코드트리 | HashMap / 순서를 바꾸었을 때 같은 단어 그룹화하기 {언어 : Python} [가장 작은 시공간복잡도]

문제 링크

https://www.codetree.ai/trails/complete/curated-cards/challenge-group-same-word/description

Code Tree | Learning to Code with Confidence

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
words = [input().strip() for _ in range(n)]

# Write your code here!
asciiDict = dict()
def makeKeys(word):
    tmpArr = [0] * 52 # 앞 26개는 대문자 뒤 26개는 소문자
    for w in word:
        ascii = ord(w)
        if ascii < 97:
            tmpArr[ascii-65] += 1
        else:
            tmpArr[ascii-71] += 1
    return "".join(map(str, tmpArr))
for word in words:
    asciiKey = makeKeys(word)
    if asciiKey in asciiDict:
        asciiDict[asciiKey] += 1
    else:
        asciiDict[asciiKey] = 1
maxCnt = max(list(asciiDict.values()))
print(maxCnt)

풀이 방법

1. ascii 코드를 활용해서 길이가 52인 문자열로 된 키를 만든다.
   • 대문자는 65 ~ 90
   • 소문자는 97 ~ 122
   • 대문자는 앞에 0 ~ 25인덱스에 저장
   • 소문자는 뒤에 26 ~ 51인덱스에 저장
   • "AZABacaz"라면
   • [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
   • 이를 하나로 합치기 전에 map을 사용해서 문자로 바꾼다.
   • join으로 합쳐서 ascii 키를 만든다.
2. 키를 asciiDict에 저장한다.
   1. 있으면 +1
   2. 없으면 1
3. values 중에 가장 큰 값을 max로 찾는다.
4. maxCnt를 출력하면 끝!

느낀점

• 문자열을 리스트로 바꾸고 정렬한 다음에 다시 뭉치고 새로 만들어진 문자열을 딕셔너리에 저장하는 방식이 떠오르지 않았다.
• 하지만 아스키 코드를 활용해서 푸는 방법을 고안했고 결국 제일 빠른 방법이 되었다.
• 이유로는 문자열의 길이가 1000이라고 가정할 때 정렬해서 join하는 것 보다 길이가 52인 배열에 저장해서 join하는 것이 더 빠르기 때문이다. 
• 이처럼 하나의 방법에 매몰되지 말고 여러 방법을 떠올리는 것이 중요하다.