230311 문자열_ 애너그램 그룹화, 가장 긴 팰린드롬

@ 파이썬 알고리즘 인터뷰 책의 내용을 다시 복기하기 위해 쓰는 글

 

애너그램 그룹화

정렬해서 사용하는 방법이 제일 쉬움

 

sorted()와 sort()의 차이 알아두기

-문자열에서는 sorted()만 가능 .sort() 안 됨

sort()하면 값 자체가 바뀜

sorted()는 리스트로 저장해서 반환

 

# sort()의 경우

# sort()의 경우
sort_test = [ 'd', 'c', 'b','a',]
sort_test.sort()
print(sort_test)

# 주의 할 것
sort_test4 = sort_test.sort()
print(sort_test4)

>>

['a', 'b', 'c', 'd']
None

#sorted()의 경우

# sorted()의 경우
sort_test2 = [ 'd', 'c', 'b','a',]
print(sorted(sort_test2))
print(sort_test2)

sort_test_len = [ 'd', 'ccc', 'bb','aaaa',]
print(sorted(sort_test_len, key=len)) #길이 순서로 sorted

sort_test_fn = [ 'adc', 'abc', 'azzzzzbb', 'bbb']
def fn(s):
    return s[0], s[-1] # 처음 글자 순서로 먼저 정렬, 그 다음 마지막 글자 순서로 정렬
print(sorted(sort_test_fn, key=fn)) 
print(sorted(sort_test_fn, key=lambda x: (x[0], x[-1])))

>>

['a', 'b', 'c', 'd']
['d', 'c', 'b', 'a']
['d', 'bb', 'ccc', 'aaaa']
['azzzzzbb', 'adc', 'abc', 'bbb']
['azzzzzbb', 'adc', 'abc', 'bbb']

sorted()의 경우 하이퍼파라미터로 key=함수 를 사용이 가능하다

함수의 정의 된 순서로 정렬 된다.

 

# 문자열의 경우

# 문자열의 경우도 list로 반환됨
# 이를 다시 문자열로 바꿔주려면 join 이용하기
sort_test3 = 'dcba'
print(sorted(sort_test3))
print(''.join(sorted(sort_test3)))

>>

['a', 'b', 'c', 'd']
abcd

join() 매소드 정리

- 리스트를 문자열로 만들어서 join 해줌

-기본 형태 ''.join()

 

collections에서 defaultdict 가져오면 어떻게 찍히나 체크해보기

from collections import defaultdict
defaultdict(list)

>>

defaultdict(list, {})

 

+ 추가로 정렬에서 사용되는 알고리즘들.. 

- 퀵정렬
- 삽입정렬
- 힙정렬
- 버블정렬
- 병합정렬
- 팀정렬 (팀소트) : 삽입정렬을 쪼개서 사용하는 정렬 _ 현재 파이썬 기반이 되는 정렬

 

코딩 풀이

 

input)

words = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']

sol)

from collections import defaultdict
def groupAnagrams(words):
    # defaultdict(list, {}) type으로 초기화
    anagrams = defaultdict(list)
    
    for word in words:
        # 정렬해서 딕셔너리에 추가
        
        # step 1. sorted(word)로 words[i]를 정렬
        # step 2. anagrams의 key로 step 1을 사용
        # step 3. anagrams의 key에 word를 append 해줌
        anagrams[''.join(sorted(word))].append(word)
        print(anagrams) # 어떻게 작동되는지 이해해보기
    
    # anagrams의 value 값만 return
    return list(anagrams.values())

groupAnagrams(words)

>>

아래는 내가 작동원리를 이해하기 위해서 찍어본 것

defaultdict(<class 'list'>, {'aet': ['ate']})
defaultdict(<class 'list'>, {'aet': ['ate'], 'abt': ['bat']})
defaultdict(<class 'list'>, {'aet': ['ate', 'eat'], 'abt': ['bat']})
defaultdict(<class 'list'>, {'aet': ['ate', 'eat'], 'abt': ['bat'], 'ant': ['nat']})
defaultdict(<class 'list'>, {'aet': ['ate', 'eat'], 'abt': ['bat'], 'ant': ['nat', 'tan']})
defaultdict(<class 'list'>, {'aet': ['ate', 'eat', 'tea'], 'abt': ['bat'], 'ant': ['nat', 'tan']})

>>  

결과

[['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]

---

가장 긴 팰런드롬 부분 문자열 출력

- 서로 공통된 가장 긴 부분 문자열 찾기 

(ex, cp949 -> utf-8 변환)

 

※ 팬런드롬은 문자열 슬라이싱 이용하면 가장 빠르게 처리됨 (자기 자신을 예외처리 할 때 사용하기)

 

input)

pal_str = 'babttonottad'
pal_str2 = 'cbbd'

sol)

def longestPalindrome(pal):
    
    # 팰런드롬 판별 및 투 포인터 확장
    # left, right를 홀수, 짝수일 때 각각 하나 씩 키워, 탐색 구간을 늘리기
    
    def expand(left, right):
        # if1 탐색 구간의 left가 0보다 작아지면 글자X 탈출
        # if2 탐색 구간의 right가 len(pal)과 같아지면 글자X 탈출
        # if3 pal[left]와 pal[right]가 같지 않으면 더 이상 팰런드롬이 아니므로 탈출
        
        while left >=0 and right < len(pal) and pal[left] == pal[right]:
            # left, right 하나씩 키우기
            left -= 1
            right += 1
        
        # 탈출을 한 순간 - 1 번째까지 팰런드롬이므로 그 string을 slicing해 return
        return pal[(left + 1):right]
    
    # 해당 사항이 없을 때 빠르게 리턴
    # check 1 pal의 길이가 1개 또는 0개이면 그 자체가 팰런드롬
    # check 2 pal 자체가 팰런드롬이면 빠르게 return 해서 시간복잡도 최악의 경우 제거
    if len(pal) < 2 or pal == pal[::-1]:
        return pal
    
    result = ''
    # 슬라이딩 윈도우 우측으로 이동
    # step 1 길이만큼 i에 1씩 더해서 탐색
    for i in range(len(pal) - 1):
        # step 2 expand 함수 불러오기, left <- i, right <-i+1 or i+2 //2칸(짝수), 3칸(홀수) 넣음
        # step 3 기존에 가장 큰 result 와 함수 expand를 통과한 두 결과값을 key=len(길이)로 비교
        # step 4 그 중 가장 큰 값을 result에 저장
        result = max(result, expand(i, i+1), expand(i, i+2), key=len)
        
    return result

print(longestPalindrome(pal_str))
print(longestPalindrome(pal_str2))

ttonott
bb