풀이를 보기전에 모든 문제에 대해 부딪혀보았다.
1,2,4,5번은 풀었고 6번은 2시간을 넘겨 풀이를 보았다.
문제를 풀이하기 전 빈 종이에 구상을 먼저 해야한다.
모르고 지나치는 예외가 있기 때문에 리트코드 문제의 예시는 2개정도가 있는 데 모든 예시에 대해서 문제에 적용해봐야 한다.
1. 유효한 팰린드롬(125)
class Solution(object):
def isPalindrome(self, s):
d = ''
for i in s:
if i.isalnum():
d = d + i
end_index = len(d) - 1
for i in range(0, len(d) / 2):
if d[i].lower() == d[end_index - i].lower():
continue
else:
return False
return True내 풀이의 속도와 메모리 점유율
이 문제를 2개의 단계로 구분하면
첫 단계는 주어진 문자열을 영문자와 숫자로 전처리하는 것이다.
내 코드에서의 전처리 부분은
d = ''
for i in s:
if i.isalnum():
d = d + i이다.
전처리를 re.sub을 이용하여 할 수 도 있는데
s = s.lower()
s = re.sub('[^a-z0-9]', '', s)정규 표현식에 알파벳과 숫자에 해당하는 것을 공백으로 하여 제거하는 것이다.
두번째 단계는 팰린드롬인지 확인하는 단계이다.
end_index = len(d) - 1
for i in range(0, len(d) / 2):
if d[i].lower() == d[end_index - i].lower():
continue
else:
return False
return True
맨 앞 인덱스와 맨 뒤 인덱스의 값을 비교한 후 맨 앞 인덱스 + 1 맨 뒤 인덱스 - 1과 비교하여
len(s) / 2까지 비교 하였다.
책에서 제시하는 방법은 첫 단계부터 다르다.
첫 단계인 문자열 전처리과정에서 문자열을 검증한 후 리스트에 담는다.
strs = []
for char in s:
if char.isalnum():
strs.append(char.lower())
두번째 단계에서도 비슷한 방식이지만 리스트로 다룬다.
while len(strs) > 1:
if strs.pop(0) != strs.pop():
return False
return Truewhile의 조건식에서 리스트의 길이가 1보다 큰 경우로 따진다.
일단 while문 내용이 리스트의 맨 앞과 맨 뒤의 요소를 제거한다는 것만 생각하고
while문의 조건식을 보면 리스트의 요소 개수가 홀 수인 경우 마지막전까지 while조건식이 True였다면
그 다음 while조건식의 len(str)은 1이 되어 False가 되고 True를 반환한다.
리스트의 요소 개수가 짝 수인 경우 마지막 조건식은 0이 되어 False가 되고 True를 반환한다.
pop함수는 리스트에서 해당하는 인덱스의 값을 삭제한 후 그 값을 반환한다.
책에서 제안하는 방법은 2가지가 더 있다.
한가지는 list대신에 collections.deque()를 사용하고 pop(0)대신에 popLeft()를 사용하는 것이다.
popLeft()를 사용하면 시간 복잡도가 O(1)이다.
import collections
class Solution(object):
def isPalindrome(self, s):
strs = collections.deque()
for char in s:
if char.isalnum():
strs.append(char.lower())
while len(strs) > 1:
if strs.popleft() != strs.pop():
return False
return Truedeque를 사용할 때 속도이다. 313ms의 1/6배이다
문자열 슬라이싱을 이용하는 방법도 있다. 이는 매우 속도가 빠르다.
class Solution(object):
def isPalindrome(self, s):
s = s.lower()
s = re.sub('[^a-z0-9]', '', s)
return s == s[::-1]
유효한 펠린드롬 문제에서 얻어갈 점은
문자열을 전처리할 때 is머시기 함수를 통해 리스트에 추가하는 방법과 re.sub함수를 이용하여 전처리 할 수 있다는 것과
맨 앞의 요소를 pop하고자 할 때 collections.deque()와 popLeft()를 사용하면 O(1)의 시간복잡도로 pop을 할 수 있으며
문자열 슬라이싱 연산을 할 경우 속도가 매우 빠르다는 것이다.
2. 문자열 뒤집기(344)
문자열을 뒤집으면 된다. 문자열을 조작해야하고 리턴이 없어야 한다.
내가 푼 방법이다. 교재의 방법보다 속도가 빠르다.
class Solution(object):
def reverseString(self, s):
end_index = len(s) - 1
for i in range(0, ((end_index + 1) / 2)):
tmp = s[end_index - i]
s[end_index - i] = s[i]
s[i] = tmp
맨 뒤의 문자와 맨 앞의 문자의 위치를 바꾸었다.
이때 tmp라는 변수에 임시로 저장한 뒤 위치를 바꾸었다.
책에서 나온 풀이이다.
class Solution(object):
def reverseString(self, s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
파이썬에서는 값을 교환할 때 a, b = b, a형식으로 값을 교환 할 수 있다.
이를 이용한 풀이이다.
마찬가지로 맨 앞과 맨 뒤를 교체한 후 맨앞 + 1 맨뒤 -1값을 교체한다.
맨 앞 + 1이 맨 뒤 -1 보다 큰 경우 while조건식이 False가 된다.
책에서 나온 파이썬 다운 방식이라고 한다.
class Solution(object):
def reverseString(self, s):
s.reverse()이 방식을 생각 못 했다.
3. 로그파일 재 정렬
로그를 재 정렬하는 문제이다.
주어진 기준은 다음과 같다.
1. 로그의 가장 앞 부분은 식별자이다.
2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.
4. 숫자 로그는 입력 순서대로 한다.
이 문제를 통해서 배운 점은 문제에서 제시한 예시를 문제의 기준을 적용하여 출력값과 비교해봐야 한다는 것이다.
제시한 예시를 모두 적용해봐야 예외부분과 보지 못한 부분들을 파악 할 수 있다.
이 문제에서 뒤 늦게 파악한 점은 2번 기준이다.
숫자로그가 뒤에 존재한다는 것을 간과하고 문제를 풀어서 시간이 많이 지체되었다.
이 문제를 풀기위한 단계는 다음과 같다.
1. 숫자로 구성된 로그와 문자로 구성된 로그를 각각 배열에 나눈다.
(숫자로 구성된 로그는 순서를 건들이지 않고 문자로 구성된 로그는 기준에 따라 sorting한 다음 그 두 배열을 합치면 답이다.)
2. 문자 로그에 대해서 sort하는 데 식별자는 순서에 영향을 끼치지 않으므로 순서가 바뀌어도 된다. 다만 문자로그가 같다면 식별자의 순서대로 sort해야한다.
즉 문자로그 순으로 sort한 뒤 문자로그가 같다면 식별자 순으로 sort하는 것이다.
'즉 문자로그 순으로 sort한 뒤 문자로그가 같다면 식별자 순으로 sort하는 것이다.' 이 부분을 처음 보았다.
리스트를 sort할 때 단순히 한가지 값을 이용하여 sort를 하였는 데, sort함수에 lambda함수를 사용할 경우 두 원소를 갖는 튜플을 전달하여 한 값이 같은 경우 다른 값으로 판단하는 신기한 방법이었다.
a = ['Z 1', 'B 2', 'A 2', 'C 2']이 리스트를 뒤에 숫자를 기준으로 sort하고 숫자가 같다면 알파벳 순으로 sort한다고 해보자.
a = ['Z 1', 'B 2', 'A 2', 'C 2']
b = sorted(a, key = lambda x: (x[1], x[0]))
print(b)
자력으로 푼 것은 아니다. 삽질을 너무 많이해서 교재의 아이디어를 이용해서 풀었다.
내 풀이와 교재 풀이가 너무 유사하여 교재의 풀이로 분석해보자.
class Solution(object):
def reorderLogFiles(self, logs):
letters, digits = [], []
for log in logs:
if log.split()[1].isdigit():
digits.append(log)
else:
letters.append(log)
letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
return letters + digits1. 숫자로 구성된 로그와 문자로 구성된 로그를 각각 배열에 나눈다.
(숫자로 구성된 로그는 순서를 건들이지 않고 문자로 구성된 로그는 기준에 따라 sorting한 다음 그 두 배열을 합치면 답이다.)
이는 주어진 logs를 순회하여 logs.split()한 값의 첫번째 요소는 숫자아니면 단어이므로 isdigit()함수를 통해 양의 정수인지 판별한 뒤 맞다면 digits 배열에 추가하고 아니라면 letters에 추가한다.
2. 문자 로그에 대해서 sort하는 데 식별자는 순서에 영향을 끼치지 않으므로 순서가 바뀌어도 된다. 다만 문자로그가 같다면 식별자의 순서대로 sort해야한다.
즉 문자로그 순으로 sort한 뒤 문자로그가 같다면 식별자 순으로 sort하는 것이다.
letters를 로그문자 기준으로 sort하고 로그문자들이 같은 경우 식별자순으로 sort한다.
이 문제에서 우선조건이 문자로그들이 될 수 있었던 것은 식별자는 순서에 영향을 끼치지 않았기 때문이다.
결국 로그문자가 같은 경우에 식별자순으로 sort하기 위한 것이다.
4. 가장 흔한 단어(819)
문자열이 주어지고, banned라는 배열에 금지된 단어들이 주어진다.
문자열에서 금지된 단어를 제외한 단어중 가장 많이 등장한 단어를 출력하면 된다.
단어에는 구두점 대소문자가 포함되어 있는 데, 구두점은 제거하고 대문자는 소문자로 바꿔서 진행한다.
나의 풀이이다.
class Solution(object):
def mostCommonWord(self, paragraph, banned):
g = {}
for i in re.sub('[^a-zA-z ]', '', re.sub('[,.]', ' ', paragraph)).lower().split(' '):
if i in banned or i == '':
continue
if i in g:
g[i] += 1
else:
g[i] = 1
g = g.items()
print(g)
g.sort(key=lambda x: x[1], reverse=True)
return g[0][0]
12ms로 상위 100%이다.
왜지...
1. 주어진 문자열을 전처리(대문자 -> 소문자, 구두점 -> '')하여 리스트에 담는다.ㅑ
2. 리스트에 단어들을 순회하여 banned에 있는 지 검증한 뒤, 객체에 추가한다.(key = 단어, value는 개수)
3. g를 키, 값쌍의 리스트로 변경 후 값을 기준으로 sort한다.
4. 맨 앞에 있는 것을 출력한다.
1. 주어진 문자열을 전처리(대문자 -> 소문자, 구두점 -> '')하여 리스트에 담는다.
re.sub('[^a-zA-z ]', '', re.sub('[,.]', ' ', paragraph)).lower().split(' ')re.sub함수를 통해 문자열을 교체하는 데, 알파벳대소문자 혹은 띄어쓰기가 아닌 경우 ''으로 교체한다.
이때 대상도 re.sub함수를 통해 교체하는 데, 구두점을 띄어쓰기로 교체한다.
이후에 lower함수로 소문자 변환을 하고 리스트로 바꾼다.
2. 리스트에 단어들을 순회하여 banned에 있는 지 검증한 뒤, 객체에 추가한다.(key = 단어, value는 개수)
g = {}
for i in re.sub('[^a-zA-z ]', '', re.sub('[,.]', ' ', paragraph)).lower().split(' '):
if i in banned or i == '':
continue
if i in g:
g[i] += 1
else:
g[i] = 1
i 값이 banned에 있는 지 검증한다. 있다면 continue한다.
아니라면 객체에 개수로 추가한다.
워낙 많이 사용하는 테크닉이므로 넘어간다.
3. g를 키, 값쌍의 리스트로 변경 후 값을 기준으로 sort한다.
4. 맨 앞에 있는 것을 출력한다.
g = g.items()
print(g)
g.sort(key=lambda x: x[1], reverse=True)
return g[0][0]g.items()는 키,값 쌍으로 리스트에 담긴 것이다.
g를 sort하는데 기준은 x[1]즉 값이다. 여기 값은 단어의 개수를 의미한다.
reverse=True는 내림차순 즉 앞에 값이 가장 크게 한다는 것이다.
그리고 인덱싱으로 가장 큰 개수를 갖는 단어를 리턴한다.
5. 그룹 애너그램(49)
내 풀이 이다.
class Solution(object):
def groupAnagrams(self, strs):
g = {}
for i in strs:
s1 = ''.join(sorted(list(i)))
if s1 in g:
g[s1].append(i)
else:
g[s1] = [i]
return g.values()
책에서의 풀이와 다른 점은 나는 직접 객체에 조건에 따라 추가하였고
책에서는 defaultdict를 이용하여 문제를 풀었다.
또한 sort함수에 문자열을 전달하면 배열로 취급한 뒤 sort하는 것을 몰랐다.
a = 'atd'
print(sorted(a))출력 ['a', 'd', 't']
따라서
s1 = ''.join(sorted(i))로 바꿀 수 있고
defualtdict를 사용한다면
import collections
anagrams = collections.defaultdict(list)
...
anagrams[''.join(sorted(word))].append(word)
return list(anagrams.value())이렇게 바꿀 수 있다.
anagrams[키].append(값)에서 defaultdict에 키가 존재하지 않는다면
디폴트인 list에 word를 추가하는 것이다.
