[1스4코2파] #127. LeetCode Algorithm Day 3 (Move Zeroes, Two Sum II - Input Array Is Sorted)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (127일차)
[4코1파] 2023.01.13~ (118일차)
[1스4코1파] 2023.04.12~ (29일차)
[1스4코2파] 2023.05.03 ~ (8일차)

Today :

2023.05.10 [127일차]

LeetCode Algorithm Day 3
283. Move Zeroes

• https://leetcode.com/problems/move-zeroes/?envType=study-plan&id=algorithm-i

167. Two Sum II - Input Array Is Sorted

• https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan&id=algorithm-i

문제 1

[283. Move Zeroes]

https://leetcode.com/problems/move-zeroes/?envType=study-plan&id=algorithm-i

내 코드

class Solution:
    def moveZeroes(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        
        n = nums.count(0)
        
        for i in range(n):
            tmp = nums.index(0)
            del nums[tmp]
            nums.append(0)
            
        return nums

문제 풀이 방법

모.. 주어진 array 에 0이 있을 수도 없을 수도 있으므로,
일단 count를 사용해서 0의 횟수를 세고, 그 횟수 만큼 loop를 돌아서,
index로 0의 자리를 찾고 제거한 후에, arr 뒤에 0을 append 해주면 됨

증빙

---

문제 2

[167] Two Sum II - Input Array Is Sorted
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan&id=algorithm-i

내 코드

class Solution:
    def twoSum(self, numbers, target):
        start,end = 0, len(numbers)-1
        answer = []
        while start < end:
            if numbers[start]  + numbers[end] == target:
                return [start+1, end+1]

            elif numbers[start]+numbers[end] <target:
                start +=1

            else:
                end -=1

        return answer

문제 풀이 방법

처음에는 bianrySearch 함수를 굳이 만들어서 인덱스를 찾아서 핸들링했는데
테스트 케이스 중에서 걸리는 문제를 보고 아,, 그냥 sum 자체로 binary Search 하면 되는 구나... 라고 해서 풀었음

뭐 일단 binary Search 처럼 start, end를 지정하고
array의 start, end index 값을 더해서 target과 같은지 비교
target 보다 합산한 값이 적으면 start 의 index를 +1 해주고,
target 보다 합산한 값이 많으면 end 의 index를 -1 해주면서 찾아나가면 됨

---

<2023.05.24 추가>

LeetCode의 1번 Two sum을 풀고나서 더 나은 풀이 발견
Two Sum을 풀 듯이 하되, tmp 딕셔너리에 인덱스보다 +1 을 추가해서 저장하면 될일..

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        tmp = {}

        for i in range(len(numbers)):

            if numbers[i] in tmp:
                return [tmp[numbers[i]],i+1]

            tmp[target - numbers[i]] = i+1

효율성 부분에서는 이 코드가 더 낫다

증빙

여담

오늘 왜 수요일
today why wednesday ?