onlybooks / python-algorithm-interview

<파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트
1.21k stars 325 forks source link

7장 7번(leetcode 1번) 질문입니다 #138

Closed heesungkim010 closed 2 years ago

heesungkim010 commented 2 years ago

안녕하세요. 책의 문제풀이 5 에서 이 문제가 인덱스 구해야하는거라 투포인터 이용하면 안된다고 하셨는데요. sorted 를 써서 따로 배열 만드는 방식으로해서 투포인터로 문제를 풀었습니다. leetcode submit에서 통과는 했는데 이렇게 풀어도 되는건지 궁금합니다.

quo, rem = divmod( target, 2)  # fast check for half the target
if rem == 0 :
    if nums.count(quo) > 1 : #half 값이 이미 두개 이상 있음. 이걸로 return하면 끝.
        half_val_indices = [index for index, x in enumerate(nums) if x == quo]
        return half_val_indices[0], half_val_indices[1]
else: pass

sorted_list = sorted(nums)
start = 0
end = len(nums) - 1

while start < end :
    if sorted_list[start] + sorted_list[end] == target :
        break
    elif sorted_list[start] + sorted_list[end] > target : # now : larger than target. so get smaller.
        end -= 1
    else : # < target
        start += 1

return [nums.index(sorted_list[start]), nums.index(sorted_list[end])]
likejazz commented 2 years ago

물론 통과한다면 어떤 풀이든 가능합니다. 그러나 저렇게 풀이할 경우 어떤 잇점이 있는지를 고민해야 하는데, 사실상 저런 형태로 풀이하면 투 포인터의 장점(시간 복잡도 등)은 얻지 못하고 단순히 투 포인터로 풀이만 한 셈이므로 좋은 풀이로 보기는 어려울거 같습니다.