[Quetion]
- 문자열에서 영문, 숫자가 아닌 것을 제외하고, 모두 소문자이어야 한다.
- 앞 뒤로 동일하게 읽히는 데칼코마니 문자열이어야 한다.
데칼코마니 = 맨 앞과 맨 뒤의 문자열을 비교해서 같으면 된다로 이해했다.
그래서 투포인터 방법으로 문제를 해결하면 되겠다고 생각했다.
생각흐름은 다음과 같다.
- 모두 소문자로 변환한다
- a-z까지 해당 할 경우 새로운 변수에 문자할당
- left, right 포인터 생성
- l과 r의 위치에 해당하는 문자열 비교 같으면 l=증가 r=감소
- 틀리면 false
class Solution(object):
def isPalindrome(self, s):
s=s.lower()
new=""
for i in s:
if i.isalnum():
new+=i
r=len(new)-1
for l in range(len(new)):
if l >= r:
break
if new[l] != new[r]:
return False
r-=1
return True
Runtime: 295ms | Memory: 16.5MB
LeetCode 코드 중 Runtime 21%, Memory 8% 해당하는 결과
lower() 함수를 활용하여 대문자를 소문자 변환
isalnum() 함수로 문자열이 영문과 숫자인지 확인
새로운 변수에 영문, 숫자만 담는 과정을 없애고 소문자를 변환하는 과정을 조건문에 더한다면, for문 1개와 변수 1개를 없앨 수 있으므로 시간복잡도 O(n), 공간복잡도 O(1)로 개선할 수 있을 것 같다.
class Solution(object):
def isPalindrome(self, s):
l,r=0,len(s)-1
while l < r:
if not s[l].isalnum():
l+=1
elif not s[r].isalnum():
r-=1
elif s[l].lower() != s[r].lower():
return False
else:
l += 1
r -= 1
return True
Runtime: 295ms ---> 24ms
Memory: 16.5MB ---> 14.87MB
기존 isalnum()함수로 for문을 돌려 새로운 변수에 저장하는 방법을 제거하고, l포인터와 r포인터를 활용하여 조건문에 할당했다.
또한 조건문을 통해 비교할 문자 값만 소문자로 변경하여 비교함으로써 전체를 소문자로 바꾸는 과정도 없앨 수 있었다.
결론적으로 Runtime과 Memory 모두 눈에 띄게 개선할 수 있었고, 이 방법으로 접근했을 때 해당 문제는 for문 보다는 while문으로 변경하니 더 깔끔한 것 같다.
[Quetion]
- 리스트는 오름차순으로 정렬되어 있다.
- 리스트의 값 중 두개의 합이 target값과 같으면 해당 값들의 인덱스+1을 반환해야 한다.
- 반환 값은 리스트 형식이다.
투포인터 접근 방법으로 생각했다.
두개의 포인터를 증감 시켜서 target값과 일치하면 결과 리스트에 추가하고 결과 리스트를 반환하면 되겠다고 생각했다.
이를 의사코드화 해보았다.
left, right 포인터 활용
리스트[l] + 리스트[r] > target이면,
right 포인터 감소리스트[l] + 리스트[r] < target이면,
left 포인터 증가리스트[l] + 리스트[r] == target
result.append(l+1)
result.append(r+1)result 반환
class Solution(object):
def twoSum(self, numbers, target):
i=0
l,r=0,len(numbers)-1
result=[]
while numbers:
if l >= r:
break
if numbers[l] + numbers[r] > target:
r-=1
elif numbers[l] + numbers[r] < target:
l+=1
else:
result.append(l+1)
result.append(r+1)
break
i+=1
return result
Runtime: 93ms | Memory: 14MB
LeetCode 코드 중 Runtime 67%, Memory 84% 해당하는 결과
시간복잡도는 O(n), 공간복잡도는 O(1)을 가지고 있다.
# 불필요한 if문, result 변수 제거
class Solution(object):
def twoSum(self, numbers, target):
l,r=0,len(numbers)-1
while l <= r:
if numbers[l] + numbers[r] == target:
return [l+1, r+1]
elif numbers[l] + numbers[r] < target:
l+=1
else:
r-=1
Runtime: 93ms ---> 88ms
Memory: 14MB ---> 14MB
불필요한 if문과 result변수를 제거하고 append()함수를 사용하지 않았다고 해서 5ms의 Runtime 개선은 있지만 효과가 미미했다. 성능적으로 크게 영향을 끼치지는 않았지만 코드가 간결해지는 효과는 얻을 수 있었다.
# 이진 검색 방법으로 접근법 변경
class Solution(object):
def twoSum(self, numbers, target):
for i in range(len(numbers)):
check = target-numbers[i]
l,r=i+1,len(numbers)-1
while l <= r:
avg = (l+r)//2
if numbers[avg] == check:
return [i+1, avg+1]
elif numbers[avg] > check:
r = avg-1
else:
l = avg+1
Runtime: 93ms ---> 137ms
Memory: 14MB ---> 14.7MB
이진검색의 방법으로 코드를 구현해보았는데 이상하게도 처음 접근법에 비해 Runtime과 Memory에서 더 좋지 않은 결과를 얻었다. 분명 이진검색의 경우 시간복잡도가 O(nlogn)으로 기존 O(n)에 비해 빨라야 된다고 생각해서 다른 솔루션들을 참고해보았다.
그 결과 현재 이진검색으로 구현한 코드에서는 한번 탐색했던 요소를 다시 탐색하는 상황이 있었고, 그렇게 될경우 O(nlogn)이 아닌 반복문 두개의 O(n^2)에 더 가깝다고 할 수 있으므로 느렸던 것이다.
# 중복 탐색 확인 duplicate list 추가
class Solution(object):
def twoSum(self, numbers, target):
duplicate = []
for i in range(len(numbers)):
if not numbers[i] in duplicate:
duplicate.append(numbers[i])
check = target-numbers[i]
l,r=i+1,len(numbers)-1
while l <= r:
avg = (l+r)//2
if numbers[avg] == check:
return [i+1, avg+1]
elif numbers[avg] > check:
r = avg-1
else:
l = avg+1
Runtime: 137ms ---> 85ms
Memory: 14.7MB ---> 14.7MB
duplicate라는 list를 추가하여 이미 탐색한 값인지 확인하는 조건문을 추가해줌으로써 중복 탐색의 경우를 배제했다.
결과적으로 가장 처음인 93ms 보다도 더 빠른 Runtime을 가질 수 있었고, 8ms의 Runtime 개선효과를 얻을 수 있었다. 하지만 duplicate라는 리스트에 값을 저장하는 상황을 추가하여 공간복잡도는 더 높아졌다.