[LEETCODE] Python3 🐍 | Easy Collections 추천문제 및 풀이 (2) Sorting&Searching, Dynamic Programming, Design, Math, Others

https://leetcode.com/explore/interview/card/top-interview-questions-easy/

Explore - LeetCode

 

 

일주일에 거쳐 푼 21문제에 대한 풀이 2탄 입니다. 

카테고리 : Sorting&Searching, Dynamic Programming, Design, Math, Others

 

11. 774 | SORTING & SEARCHING | First Bad Version

https://leetcode.com/submissions/detail/644530078/?from=explore&item_id=774 

Account Login - LeetCode

불량품 이후로는 다 불량품만 나온다고 할 때, 첫번째 불량품의 인덱스를 찾는 문제입니다.
간단하게 binary search로 풀었습니다.

# The isBadVersion API is already defined for you.
n, bad = 1, 1
def isBadVersion(version: int) -> bool:
    # print("v", version)
    if bad <= version: return True
    else: return False

class Solution:
    def firstBadVersion(self, n: int) -> int:
        def bs(st, ed):
            if st > ed: return st
            mid = (st+ed)//2
            if isBadVersion(mid):
                return bs(st, mid-1)
            else:
                return bs(mid+1, ed)
        return bs(1, n)

print(Solution().firstBadVersion(n))

 

12. 569 | DYNAMIC PROGRAMMING | Climbing Stairs

https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/ 

cache = {0 : 1, 1: 1}

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 0: return 0
        if n in cache: return cache[n]
        cache[n] = self.climbStairs(n-1)+self.climbStairs(n-2)
        return cache[n]

n = 3
print(Solution().climbStairs(n))
print(cache)

 

13. 572 | DYNAMIC PROGRAMMING | Best Time to Buy and Sell Stock

https://leetcode.com/submissions/detail/644568471/?from=explore&item_id=572 

주식 매도/매수 최적 시기를 찾는 문제입니다. 

한 번만 샀다 팔 수 있으므로, 큰 수가 뒤에 나오면서 가장 차이가 많이 나는 숫자 Pair를 찾으면 됩니다.

from typing import List

# 현재까지 가장 작은 수 기록
# 최대이율 기록
# 가장작은수보다 더 작은거 나오면 작은수 리셋

prices = [7,1,5,3,6,4]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        least = prices[0] if len(prices) > 0 else 0
        for i in prices:
            if i < least: least = i
            if i-least > maxProfit: maxProfit = i-least
        return maxProfit
print(Solution().maxProfit(prices))

 

14. 566 | DYNAMIC PROGRAMMING | Maximum Subarray

https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/566/

배열의 연속된 숫자 합이 가장 클 때 그 합을 구하는 문제입니다.

 

처음에는 n^2 경우의 수에 대해 합을 다 구하는 단순한 방법으로 풀었다가 TLE를 맞았습니다.. ㅜㅜ

 

subarray의 sum이 0보다 작다면, 이전 값들은 버리고 다시 subarray를 구성하는 것이 당연히 값이 더 크겠죠.

이 아이디어를 활용하여 아래 코드를 짰습니다.

from typing import List

nums = [-2,1,-3,4,-1,2,1,-5,4]
nums = [-1, 1, -3, -4]
# nums = [-1,1,2,1]
nums = [5,4,-1,7,8]
cache = {}
class Solution:
    ## TLE
    # def maxSubArray(self, nums: List[int]) -> int:
    #     Matrix = [[0 for x in range(len(nums))] for y in range(len(nums))]
    #     max = nums[0]
    #     for i in range(len(nums)):
    #         for j in range(i, len(nums)):
    #             if i is j:
    #                 Matrix[i][j] = nums[i]
    #             else:
    #                 Matrix[i][j] = Matrix[i][j-1] + nums[j]
    #             if Matrix[i][j] > max: max = Matrix[i][j]
    #     return max

    def maxSubArray(self, nums: List[int]) -> int:
        subSum = maxSum = 0
        for i in nums:
            subSum = i + subSum
            if subSum > maxSum: maxSum = subSum
            if subSum < 0: subSum = 0
        if maxSum is 0:
            return max(nums)
        return maxSum

print(Solution().maxSubArray(nums))

 

15. 670 | DESIGN | Shuffle An Array

https://leetcode.com/explore/interview/card/top-interview-questions-easy/98/design/670/

Design쪽 문제는 두문제 다 쉽습니다.

문제 자체는 그냥 random shuffle하는 함수 하나만 만들면 되요.

 

다만 평소에 python으로 코딩을 하지는 않아서 class만들고 이런걸 어떻게 하는지 좀 찾아보면서 풀었습니다.. ㅎㅎ

from typing import List
import random

class Solution:
    def __init__(self, nums: List[int]):
        self.arr = nums
        self.len = len(nums)

    def reset(self) -> List[int]:
        return self.arr

    def shuffle(self) -> List[int]:
        return random.sample(self.arr, self.len)

# Your Solution object will be instantiated and called as such:
obj = Solution([1, 2, 3])
param_1 = obj.reset()
param_2 = obj.shuffle()
print(param_1)
print(param_2)

 

16.562 | DESIGN | Min Stack

https://leetcode.com/explore/interview/card/top-interview-questions-easy/98/design/562/

getMin마다 stack의 Min값을 구해도 TLE없이 통과되기는합니다.

하지만 더 나은 방법은 아래와 같이 min값 전용 stack을 따로 구성하고 있는 것입니다.

min stack에는 현재까지 값 중 가장 작은값을 넣어줍니다.

 

Ex)

Stack : 5 7 4 5 3

Min    : 5 5 4 4 3

 

pop시에는, stack과 min에서 둘 다 pop을 해주고 

getMin에서는 min[-1]값을 주면 되서 O(1)에 해결 가능합니다. 

class MinStack:
    def __init__(self):
        self.stack = []
        self.min = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        minval = min(self.min[-1], val) if self.min else val
        self.min.append(minval)

    def pop(self) -> None:
        self.stack.pop()
        self.min.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min[-1]
        
# Your MinStack object will be instantiated and called as such:
obj = MinStack()
obj.push(-2)
obj.push(0)
obj.push(1)
print(obj.getMin())
print(obj.top())
print(obj.getMin())

 

17. 744 | MATH | Count Primes

https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/744

이 문제는 다른 글에서 따로 다루겠습니다.

 

 

18. 745 | MATH | Power Of Three

https://leetcode.com/explore/interview/card/top-interview-questions-easy/102/math/745/

주어진 숫자가 3의 n승인지 확인하는 문제입니다. 한 번 3의 n승이 나오면 캐싱해두도록 풀었습니다.

캐싱한 마지막 숫자보다 작은데 리스트에 없으면 3의 n승이 아닙니다.

 

1. 나눈 값에  int() 안씌워서, 2. 1이 인풋으로 들어올때를 고려 안해서 WA먹었습니다 ㅜㅜㅜㅜ

import math
class Solution:
    def __init__(self):
        self.powerOfThreeList = [1, 3]
    def isPowerOfThree(self, n: int) -> bool:
        # print(n)
        if n in self.powerOfThreeList: return True
        if n > self.powerOfThreeList[-1]:
            isPowerOfThree = n%3 is 0 and self.isPowerOfThree(int(n/3))
            if isPowerOfThree:
                self.powerOfThreeList.append(n)
                self.powerOfThreeList.sort()
            return isPowerOfThree
        return False

sol = Solution()
# print(sol.isPowerOfThree(9))
# print(sol.isPowerOfThree(10))
# print(sol.isPowerOfThree(11))
# print(sol.isPowerOfThree(27))
print(sol.isPowerOfThree(1))

 

19. 745 | Others | Number of 1 Bits

https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/565/

시프트연산을 활용하는 문제입니다. 평소에 개발할때는 시프트 연산을 쓸일이 잘 없는데.. 코테에는 이렇게 한번 씩 나오더라구요. 

시프트연산은 다른 연산에 비해 속도가 빠른 것으로 알고 있습니다.

개념이 어렵진 않아서 한 번 알아두면 관련 문제 만났을 때 유용하게 쓰는 것 같습니다.

 

두번째 풀이는 discussion에서 배껴온건데, 파이썬이여서 가능한 한줄짜리 풀이.. ㅎㅎ 이런거 찾아보는것도 재밌죠.

## 시프트연산 활용
class Solution:
    def hammingWeight(self, n: int) -> int:z
        ret = 0
        while n:
            ret += n & 1
            n = n >> 1
        return ret

## python bin()
class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')


print(Solution().hammingWeight(3))

 

20. 721 | Others | Valid Parenthesis

https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/721/

스택을 활용하는 대표적인 문제죠.

여는괄호일때는 스택에 넣고, 닫는괄호일때는 스택에 마지막 값과 매칭하는지 확인하고 pop()합니다.

 

스택 쓸때는 element없을 때 pop() 하는 부분 예외처리 안해서 꼭 한번씩 runtime error를 먹게 되네요.. ㅜㅜ

class Solution:
    def isValid(self, s: str) -> bool:
        matching_pair = {"]" : "[", "}": "{", ")": "("}
        opening_parenthesis_stack = []
        for c in s:
            if c in ["[", "{", "("]:
                opening_parenthesis_stack.append(c)
            else:
                if not len(opening_parenthesis_stack ) > 0: return False
                opening_parenthesis = opening_parenthesis_stack.pop()
                if matching_pair[c] is not opening_parenthesis: return False
        return len(opening_parenthesis_stack) is 0

print(Solution().isValid("()[]{}"))
print(Solution().isValid("()[]{"))
print(Solution().isValid("{]"))
print(Solution().isValid("]"))

 

 

이제 easy 다 풀었으니 medium으로 넘어갑니다~!