[Leetcode] TwoSum

ssuh0o0·2022년 2월 13일
0

Leetcode

목록 보기
2/3

🎈 처음 Leetcode 들어가봤다

릿코드를 처음 들어가봤다. 여기저기서 익히 들었어서 알고 있었지만, 프로그래머스를 풀고 있었기 때문에, 굳이 들어가보진 않았었다. 그러다가 프로그래머스가 갑자기 너무 하기싫고, 그렇지만 하루에 무언가라도 하고싶었기 때문에, 고민하다가 릿코드에 들어가 보게 되었다. 가자마자 든 생각.. 영어공부 열심히 해야겠다... ㅋㅋㅋㅋㅋㅋ라는 것이었다.
그래도 보다보니, 프로그래머스와는 다르게, 속도나 메모리에 더 신경써서 알고리즘을 풀 수 있다는 것에 흥미가 생겼다.

📌 문제 내용

📌 예시

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
Input: nums = [3,3], target = 6
Output: [0,1]

📌 내가 작성한 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
             for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]                    

🧸 풀이 설명

먼저, 처음에는 조합을 쓰려고 했다. 문제에 2개의 합으로만 해당 target을 만족시키면 돼서, 조합을 써서 그 해당 조합만 확인해야겠다라고 생각했었다.
근데 문제가 생겼다. 세번째 예시에 보면, [3,3] 이렇게 같은 숫자가 배열에 있는데, 조합으로 확인하면 그 값에 해당하는 인덱스를 index로 찾게 되는데, 이렇게 되니까 자꾸 [0.0]이 나오게 되는 상황이었다. 그래서 다시 코드를 갈아엎었다.
생각나는게 for문 두개로 돌리는 방법 + 더한 값이 target일때 return을 바로 시켜서 break를 걸어주는 방법이라 위 코드처럼 작성하였다.

📚 추가 공부

막상 돌려보니, 속도도 중간, 메모리 사용도 중간 정도가 나왔다.

근데, 속도가 200도 안되는 사람이 너무나도 많은 것이었다. 그래서 이건 무조건 다른 코드를 찾아봐야겠다 싶어서 찾아봤다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nlist = {}
        for i, j in enumerate(nums):
            if target - j in nlist:
                return [nlist[target-j],i]
            nlist[j] = i

위 코드를 돌리면 아래와 같은 속도가 측정된다.

위의 코드는 dictionary를 써서, 해당 값을 찾는 것을 확인했다. 프로그래머스를 풀면서, 인덱스가 무조건 유지되어야 하는 상황에서 dictionary를 주로 썼는데, 이런상황에서도 쓰일 줄 몰랐다. 이렇게 쓰니까 엄청 빨랐다. 아마도 for문 하나를 if문으로 대체해서 찾기 때문에, 훨씬 줄어든 것이 아닐까 싶었다.
오늘도 하나 배웠다😀

profile
🐻‍❄️

0개의 댓글