아스

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 937번 ( https://leetcode.com/problems/reorder-data-in-log-files/ )

풀이방법 1. 

파이썬에서 기본으로 제공하는 정렬함수 sort를 이용하고, key 파라미터를 이용해서 정렬 기준을 함수나 람다표현식(lambda expression)으로 제공한다. 

sort() 함수는 리스트 자료형에만 사용할 수 있다. 만약 문자열을 sort() 함수로 정렬하고 싶다면 문자열을 리스트로 바꾼 뒤, 해당 리스트를 정렬하고, 다시 join() 등의 함수를 사용해서 리스트를 문자열로 바꾸는 작업이 필요하다.

또한 sort() 함수는 리스트 내부를 정렬한 뒤 값을 리턴하지 않는다. 

반면 sorted() 함수는 리스트를 포함한 iterable(for loop를 사용해서 자신이 가진 원소들을 한 번씩 반환할 수 있는 자료구조)에 사용할 수 있다. 여기에는 set, dictionary 등도 포함된다. 

또한 sorted() 함수는 주어진 iterable 내부를 정렬하지 않고, 새로 iterable을 만든 뒤 정렬해서 값을 리턴한다. 

sort(key=None, reverse=False)

sort(), sorted() 함수는 key와 reverse 파라미터 값을 선택적으로 받을 수 있다. 

reverse=True이면 값을 내림차순으로 정렬하고, reverse=False면 값을 오름차순으로 정렬한다. 기본값은 reverse=False이다. 

key 파라미터의 값으로는 람다식이나 함수가 올 수 있다. 람다식도 결국은 함수의 일종이니, 함수만 올 수 있는 셈이다. 

람다식은 이름 없는 익명 함수와 같으며, lambda 키워드를 사용해서 선언할 수 있다. 

lambda 변수이름 : 함수 식

lambda x : x+10			# 1 variable
lambda [x, y] : x+y		# multiple variables

로그 파일 정렬도 로그 파일 문자열을 단순 abc 정렬한 순서가 아니라, 두 번째 단어 이후의 문자 순서대로 정렬하고, 모든 문자열이 같을 경우만 첫 번째 단어를 고려하여 결정한다. 따라서 이 경우 sort() 함수에서 key 파라미터 값에다가 (두 번째 단어 이후의 문자열 + 첫 번째 단어의 문자열)을 리턴하는 함수를 할당하면, 해당 기준에 맞게 정렬할 수 있다. 

letters.sort(key=lambda x:(x.split[1:], x.split[0]))

참고한 포스트

https://docs.python.org/3/howto/sorting.html

https://docs.python.org/3/reference/expressions.html

https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Iterables.html -> iterable의 정의 참고

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

leetcode 344번 ( https://leetcode.com/problems/reverse-string/ )

풀이방법 1. 

투 포인터를 사용한다. left 포인터는 문자열의 맨 처음에, right 포인터는 문자열의 맨 끝에 두고 다중 할당 방식을 이용해서 바꾼다. 

파이썬에서 두 변수의 값을 바꿀 경우, 다른 언어들과는 달리 다중 할당을 이용해야 한다. 그렇지 않으면 예상하던 결과가 나오지 않을 수 있다. 파이썬에서는 다른 언어들과 달리 한 변수가 다른 변수에 할당될 때 값을 복사(call by value)하지 않고 값을 참조(call by reference)하기 때문이다. 

값을 복사하는 다른 언어의 경우, 임시로 값을 저장할 다른 변수를 만들어서 swap 한다. 

int a = 1; int b = 2;

// swap
int temp = a;
a = b;
b = temp;
System.out.println(a);	# 2
System.out.println(b);	# 1

반면 값을 참조하는 파이썬의 경우, 다중 할당을 이용한다. 

a = 1
b = 2
# swap
a, b = b, a
print(a, b)	# 2, 1

풀이방법 2. 

파이썬에서 기본으로 제공하는 함수를 사용한다. 

string.reverse()

text = "hello"
print(text.reverse())	# olleh

문자열이므로 기본 함수를 사용하지 않고 문자열 슬라이싱으로도 풀 수 있다. 

text = "hello"
print(text[::-1])	# olleh

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

- leetcode 125번 ( https://leetcode.com/problems/valid-palindrome/ )

풀이방법 1. 

문제에서는 팰린드롬은 영문자와 숫자만을 대상으로 한다고 했으므로, 조건에 맞는 문자들만 리스트에 넣는다. 

이후 리스트의 맨 앞과 맨 뒤의 원소를 각각 제거한 다음, 두 원소의 값이 같은지를 비교한다. 

값이 하나라도 다르면 앞뒤가 똑같지 않은 것이므로 False를, 전부 같으면 True를 리턴한다. 

파이썬에서 기본으로 제공되는 isalnum() 메소드를 사용하면 특정 문자가 alphanumeric(영문자와 숫자)인지 아닌지를 간단하게 구분할 수 있다. 

파이썬에서 제공하는 기본 메소드들은 내부적으로 속도가 훨씬 빠른 C언어를 통해 구현되어 있다. 따라서 직접 파이썬의 for loop로도 코드를 만들 수 있겠지만 기본 메소드를 사용하는 것이 더 속도가 빠르다. 

풀이방법 2. 

더 효과적인 데크(deque) 자료형을 사용한다. 

데크와 리스트의 차이점은 맨 앞의 원소를 제거하는 popleft(), pop(0) 메소드에 걸리는 시간이다. 

데크는 투 포인터라서 pop()와 popleft()이 모두 O(1)인 반면, 리스트는 pop()에는 O(1)이 소요되지만 pop(0)에는 리스트 전체 중 0번째 인덱스를 직접 찾는 셈이 되므로 O(n)이 소요된다. 

데크 자료형은 외부 라이브러리가 아닌 collections 라이브러리를 사용하며, 간단하게 선언할 수 있다.

deque = collections.deque()

collections 라이브러리에는 deque 외에도 편리한 기능이 갖춰진 기본 자료구조를 갖고 있기 때문에 공식문서를 참고해서 알아두면 좋겠다. 

https://docs.python.org/3/library/collections.html

풀이방법 3. 

정규식으로 조건에 맞는 문자들만 필터링한 다음, 문자열 슬라이싱으로 비교하는 방법도 있다. 

특히 문자열의 경우 슬라이싱(slicing)을 사용할 수 있는지 고려해보자. 생각보다 다양한 슬라이싱 방법들이 많다. 

정규식으로 문자열을 필터링하고 싶은 경우 re 라이브러리를 사용한다. 

https://docs.python.org/3/library/re.html

re.sub(정규식 패턴, 대체할 문자열, 원본 문자열)

re 라이브러리의 sub 메소드는 원본 문자열 중 패턴에 일치하는 문자열을 대체할 문자열로 바꾸는 역할을 한다. 

result = re.sub(r"[a-zA-Z]", "eee", "abc123def")
print(result)	# 'eee123eee'

문자열 슬라이싱

가장 기본적인 방법으로는 문자열의 특정 왼쪽 인덱스부터 특정 오른쪽 인덱스까지를 가져올 수 있다. 

string[left: right] 은 string 변수의 left 번째 인덱스부터 (right-1)번쨰 인덱스까지를 가져온다. 

string = "little red riding hood"
print(string[7:10])	# red

또는 인덱스에 음수를 사용하면 오른쪽 인덱스부터 왼쪽 인덱스까지, 역수 방향으로 문자열을 가져올 수 있다. 

text = "olleh"
print(text[-2:-4])	# el

문자열 전체를 뒤집거나, n칸씩 뛰어넘어서 문자열을 가져오는 것도 가능하다. 

text = "hello"
print(text[::-1])	# olleh

또는 문자열 슬라이싱으로 기존 문자열을 복사할 수도 있다. 이는 기존의 문자열의 값을 가져오고 싶으나 참조하게 되는 문제로 원본 값을 가져오지 못할 때, 참조가 아니라 값을 복사하기 위해서 사용할 수 있다. 

text = "text"
print(text[:])	# text

참고한 포스트

https://ponyozzang.tistory.com/335