(5/23) Leetcode - 알고리즘 면접 준비

121. Best Time to Buy and Sell Stock

Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        answer, min_val = 0, float('inf')

        for price in prices:
            if price < min_val:
                min_val = price
            answer = max(answer, price - min_val)

        return answer

Feedback

• 이정도는 보자마자 바로 구현을 할 수 있어야 함
• 문제를 어떻게 풀지 문제를 보고 카테고리(풀이법)를 생각해볼 것

Description

• 저가~고가 사이의 차익을 몇 구간씩 나눠서 기록해두며 최대 차익을 갱신해 나간다. (구간을 나누는 기준은 저가)
• 시간복잡도는 O(n): n에 비례해서 모든 과정의 시간이 증가한다.
• 공간복잡도는 O(1): answer와 min_val만 있으면 되므로

268. Missing Number

Link: https://leetcode.com/problems/missing-number/

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        _sum = (n * (n + 1)) // 2
        for no in nums:
            _sum -= no
        return _sum

Feedback

• 처음에 _sum을 구할 때 sum([no for no in range(n+1)])로 구했는데 이런건 공식을 찾아서 O(1)로 계산할 수 있도록 하기

Description

• 시간복잡도는 O(n): n에 비례해서 전체적인 시간이 증가한다.
• 공간복잡도는 O(1): n과 _sum만 있으면 되므로

139. Word Break

Link: https://leetcode.com/problems/word-break/

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)

        f = [False] * (len(s)+1)
        f[0] = True

        for tail in range(1, len(s)+1):
            for head in range(tail):
                if f[head] and s[head:tail] in word_set:
                    f[tail] = True
                    break

        return f[len(s)]

Description

• 1 ~ s.length까지 움직이는 tail이라는 포인터와, s의 head부터 tail까지의 substring를 사용하여 체크해나간다.
• f[head]는 현재 체크하려는 s[head:tail] 이전까지의 substring이 체크가 되었는지 여부를 나타낸다.
• 시간복잡도는 O(m*n*n)
  • wordDict만큼 O(m), s의 길이의 제곱만큼 O(n^2), 따라서 O(m*n*n)인데, wordDict의 길이가 길어질수록 O(n^3)에 가까워진다.
• 공간복잡도는 O(m*n)
  • wordDict만큼 O(m), s의 길이에 따라 생성된 f의 길이만큼 O(n), 따라서 O(m*n)인데, wordDict의 길이가 길어질수록 O(n^2)에 가까워진다.

Note

• 시간복잡도를 말할 때는 보통 최악의 경우를 생각해서 말할 것
  • 최악의 경우에는 O(n)이지만 감소하는 경우에는 그것에 따라 다르다고 말하면 됨
  • 랜덤으로 주어졌을 때도 n에 비례해서 증가하기 때문에 O(n)이라고 말해야 함
• 지금 짠 알고리즘이 무엇에 비례해서 증가하는지가 중요하다. (입력 값의 길이 n)
  • O(n)에서는 소요시간이 n에 비례해서 증가한다
    • n이 1증가 했을 때 시간이 10시간이 증가함
    • n이 2증가 했을 때 시간이 20시간이 증가함
• 같은 시간 복잡도라도 더 보기 쉬운 코드가 더 좋고, 더 깔끔한 코드에 점수를 더 준다.
• 코딩테스트에서는 문제를 정의하는 과정도 평가에 포함되므로, 제약사항도 꼼꼼히 체크할 것