오뚝이개발자

파이썬 문자열 정렬, 문자열 리스트 정렬, anagram 찾기 본문

코딩 테스트/리트코드

파이썬 문자열 정렬, 문자열 리스트 정렬, anagram 찾기

땅어 2021. 1. 14. 16:29
728x90
300x250

 

파이썬에서 사전순으로 문자열들을 정렬하기는 쉽다. sort()를 사용하면 정렬이 된다. sorted()를 사용하면 원본 리스트를 변경하지 않고 정렬이 가능하다.

a = ['cd', 'ef', 'ab']

a.sort()
print(a)	# ['ab', 'cd', 'ef']

 

하지만 만약 문자열 자체를 정렬할 필요가 있는 경우 파이썬에서는 어떻게 해야할까? 예컨대, s="adfe"라는 문자열을 정렬해서 "adef"로 만들려고 한다. 

s = "adfe"

s1 = s.sort()			# wrong
s2 = sorted(s)			# ['a','d','e','f'] 
s3 = ''.join(sorted(s))		# "adef"

 

  1. 먼저 그냥 s.sort()를 쓰면 안된다. - str type에 sort()라는 메소드가 없기 때문(이유는 string의 경우 첫글자의 주소값으로 참조를 하기에 원본이 변경되면 안된다.)

  2. 대신 sorted(s)처럼 쓰는 것은 가능하다. - 대신 return type은 list이다.

  3. 이를 하나로 이어진 문자열로 만들기 위해선 ''.join을 사용하면 된다.

 

이를 사용할 수 있는 예시 문제는 다음과 같다. 만약 words=['tea', 'ate', 'eat', 'nat', 'bat', 'tab']가 있고 이 중 anagram인 것을 찾아 묶으려 한다. 결과적으로 ans=[['tea', 'ate', 'eat'], ['nat'], ['bat', 'tab']] 처럼 만들고자 한다. (참고로, anagram이란 알파벳을 재배열하여 만들 수 있는 경우를 말한다. 만약 s1의 알파벳을 재배열해 s2를 만들 수 있다면 둘은 anagram이다.)

 

이 문제를 풀기 위해선, anagram 관계에 있는 문자열들을 구분해야 한다. 이 때, 문자열 정렬을 사용하면 된다. 예를 들어, 'tea', 'ate', 'eat'는 정렬하면 모두 'aet'이다. 따라서 이 세 문자열이 anagram임을 알 수 있다.

 

관련문제

leetcode.com/problems/group-anagrams/

728x90
300x250

'코딩 테스트 > 리트코드' 카테고리의 다른 글

3Sum  (0) 2021.07.24
Integer to Roman  (0) 2021.07.17
트리 순회(Tree traversal) 두 가지 구현 방법(재귀, 반복문)  (0) 2021.01.14
linked list 정렬하기  (0) 2021.01.03
Finding Anagrams(anagram 찾기)  (0) 2021.01.03
Comments