LeetCode[ 167 | Python ] Two Sum II - Input Array Is Sorted
업데이트:
문제
인덱스가 1 부터 시작하는 오름차순 배열 numbers와 정수 target이 주어지면 numbers 안의 두 요소를 더했을 때 target을 만들 수 있는 두 수의 인덱스를 반환해야하는 문제.
풀이
처음 고려한 것은 브루트 포스였으나, 입력이 30000 이하로 주어지는 점, 구현했을 때의 시간 복잡도가 O(n**2)가 소요될 점을 고려해 O(n)으로 해결할 수 있는 투 포인터로 해결했다.
시도
- 현재의 합을 저장하기 위해 cur 을 사용한다.
l,r포인터를 사용해 리스트를 탐색한다.- 현재의 합
cur이target보다 큰 동안에만 포인터r을 감소시킨다. - 감소된 포인터
r이 가리키는 값 만큼 현재 합을 변경한다. - 이 때
cur이target과 같아지면 주소를 반환한다.
- 현재의 합
이 풀이는 cur 과 target을 중복적으로 검사한다는 문제점이 있다고 판단되었다.
또, 마찬가지로 내부 반복문의 반복마다 대조를 하다보니 필요 이상으로 대조한다.
이미 cur > target 조건으로 판단할 수 있는데도 말이다.
그래서인지 133ms의 실행시간, 메모리의 경우 14.2MB를 달성했다.
class Solution(object):
def twoSum(self, numbers, target):
l, r = 0, len(numbers) - 1
cur = 0
while l < r:
cur = numbers[l] + numbers[r]
if cur == target:
return [l + 1, r + 1]
while cur > target and l < r:
r -= 1
cur = numbers[l] + numbers[r]
if cur == target:
return [l + 1, r + 1]
l += 1
개선
위에서 느낀점을 개선했다.
먼저 내부 while 문에서 cur을 덮어 씌우지 않고 r이 가리키는 값만큼 추가하고, 차감했다.
또한 cur > target의 조건이 이미 걸려있으므로 반복문 안에서 대조하지 않고 내부 반복문이 종료된 후 대조하게끔 변경했다.
결과적으로 실행시간이 절반 정도에 가깝게 감소된 79ms, 메모리는 크지 않은 차이로 14.1MB가 소요되었다.
class Solution(object):
def twoSum(self, numbers, target):
l, r = 0, len(numbers) - 1
while l < r:
cur = numbers[l] + numbers[r]
while cur > target:
cur -= numbers[r]
r -= 1
cur += numbers[r]
if cur == target:
return [l + 1, r + 1]
l += 1
생각 & 정리
문제를 풀이하고 투포인터 내에서도 선형 탐색이 아닌 시간 복잡도 O(logN)이 소요되는 이분 탐색으로 진행했으면 성능을 더 올릴 수 있었을 것이라는 생각이 들었다.
물론 알고리즘 대회를 준비하는 것이 아니기 때문에 극단적인 성능 향상을 도모할 필요가 없다고 생각되어 진행하진 않았지만,
말 그대로 극단적이게 성능을 향상하기 위해서는 사용하지 않았을까 ?
반면, 실제 프로젝트에 알고리즘을 도입하는 경우를 떠올렸다. 성능도 정말 중요하지만 만약 코드가 한눈에 보이지 않거나
이해할 수 없는 로직으로 짜여져있다면 이를 보수하기가 쉽지 않을 것 같다.
분명 실무에서는 성능과 가독성 그 어디께 쯤을 타협하여 작성하겠지만, 성능을 조금이라도 높여야 하는 상황이 온다면 어떤식으로 대처해야 될지 잠깐 생각하게 되는 문제였다.
댓글남기기