leetcode 122(그리디), 121(구현?), 219(구현), 13(구현)

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

오랫만에 보는 기초적인 그리디 문제이다.

class Solution(object):
    def maxProfit(self, prices):
        if not prices:
            return 0
        
        p = 0
        for i in xrange(1, len(prices)):
            if prices[i] > prices[i-1]:
                p += prices[i] - prices[i-1]
        return p

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

O(n)으로 풀어야 시간초과가 안 걸린다.

class Solution(object):
    def maxProfit(self, prices):
        if not prices:
            return 0
         
        _min,_max = 999999,-1
        for i in xrange(len(prices)-1):
            _min = min(prices[i], _min)  # 가격들중 가장 작은 값을 계속 업데이트해준다.
            _max = max(prices[i+1] - _min, _max)  # 뒤에 가격들중 가장 큰 값을 계속 업데이트해준다.
        return _max if _max != -1 else 0

219 https://leetcode.com/problems/contains-duplicate-ii/

딕셔너리에 nums배열의 값 v에 대해 가장 최신 위치들을 업데이트해준다. 그후 동일한 값이 나타나면 가장 최근의 위치와 현재 위치의 차이를 계산해서 k와 비교한다.

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        temp = {}
        for i,v in enumerate(nums):
            if v not in temp:
                temp[v] = i
            elif i - temp[v] <= k:
                return True
            temp[v] = i
        return False

13 https://leetcode.com/problems/roman-to-integer/

구현 문제이다. 주의할 점은 일반적으로 왼쪽부터 오른쪽 순으로 큰 숫자가 먼저 나오는데, 작은 수가 먼저 나올 경우 바로 뒤의 수 - 이전의 수로 해서 계산해야한다는거다. 그래서 IV는 4다. 코드짜는시간보다 문제 이해하는시간이 더 오래걸렸다.

class Solution(object):
    def romanToInt(self, s):
        if not s:
            return 0
        
        roman_dict = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D':500, 'M': 1000}
        num = 0
        i = 0
        while i < len(s)-1:
            if roman_dict[s[i]] < roman_dict[s[i+1]]:
                num += (roman_dict[s[i+1]] - roman_dict[s[i]])
                i += 2
            else:
                num += roman_dict[s[i]]
                i += 1
        if i == len(s)-1:
            num += roman_dict[s[i]]
        return num

근데 discussion을 보면 신기한 아이디어가 많다.

1. https://leetcode.com/problems/roman-to-integer/discuss/264743/Clean-Python-beats-99.78.

IV같은건 IIII로 전부 replace해서 그냥 다 더함

2. https://leetcode.com/problems/roman-to-integer/discuss/450264/Python-Beginner-98-fast-100-Memo

거꾸로 돌면서 IV같은건 빼는 로직을 적용함.