[leetcode] 150, 152, 326, 344

326. Power of Three

https://leetcode.com/problems/power-of-three/

My Answer 1: Accepted (Runtime: 72 ms - 79.18% / Memory Usage: 14.1 MB - 77.07%)

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n != 0 and n%3 == 0:
            n //= 3
        
        if n == 1:
            return True
        return False

n 을 3 으로 계속 나눴을 때, 3 의 제곱수라면 최종적으로 1 이 됨

마지막 n 이 1 인지 판단해서 T/F return

Solution 1: Accepted (Runtime: 56 ms - 99.14% / Memory Usage: 14.2 MB - 48.79%)

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if not n or n<0:
            return False

        return (math.log10(n)/ math.log10(3)) % 1 == 0

Follow up: Could you solve it without loops/recursion?

를 만족하는 루션이

(log10(n)/ log10(3)) % 1 이 0 이면 3 의 제곱수 라네요

---

344. Reverse String

https://leetcode.com/problems/reverse-string/

My Answer 1: Accepted (Runtime: 208 ms - 29.26% / Memory Usage: 18.2 MB - 98.92%)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s)//2):
            s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i]

반 나눠서 swap

My Answer 2: Accepted (Runtime: 196 ms - 76.14% / Memory Usage: 18.3 MB - 98.92%)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

reverse() 함수도 가능~

---

150. Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/

My Answer 1: Accepted (Runtime: 68 ms - 56.29% / Memory Usage: 14.7 MB - 23.05%)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op = ["+", "-", "*", "/"]
        lists = []
        for i in range(len(tokens)):
            if tokens[i] not in op:
                lists.append(int(tokens[i]))
            else:
                b = lists.pop()
                if tokens[i] == op[0]:
                    lists[-1] += b
                elif tokens[i] == op[1]:
                    lists[-1] -= b
                elif tokens[i] == op[2]:
                    lists[-1] *= b
                elif tokens[i] == op[3]:
                    lists[-1] = int(lists[-1] / b)
        
        return lists[-1]

숫자일 때만 lists 에 저장하다가
연산자를 만나면 lists 에서 하나 pop() => b
b 와 lists[-1] 과의 연산 진행 => lists[-1] update

아니면 pop() 을 두번해서 a, b 잡고 계산한 후 다시 append 해줘도 된다

python 은 / 만 하면 float 형이기 때문에 int 형으로 변환
// 를 사용하면 올림됨 ex) 0.2 => 1

---

152. Maximum Product Subarray

https://leetcode.com/problems/maximum-product-subarray/

My Answer 1: Time Limit Exceeded (186 / 187 test cases passed.)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        def func(n, p):
            if p > self.ans:
                self.ans = p
                
            if len(n) == 0:
                return
            
            func(n[1:], p*n[0])
            
        self.ans = -11
        for i in range(len(nums)):
            func(nums[i+1:], nums[i])
        
        return self.ans

nums 의 최솟값이 -10 이므로 self.ans 는 -11 로 초기화

각 숫자마다 자신을 시작으로 오른쪽에 있는 값들을 모두 곱해감 => p
p 중에 큰 값만 self.ans 에 update

이 외에도 투포인터나 dp 를 써보려고 했는데 잘 안됨...ㅎ

KADANES ALGORITHM

Solution 1: Accepted (Runtime: 64 ms - 21.23% / Memory Usage: 14.3 MB - 86.52%)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ## RC ##
        ## APPROACH : KADANES ALGORITHM ##
        
		## TIME COMPLEXITY : O(N) ##
		## SPACE COMPLEXITY : O(1) ##
        
        # 1. Edge Case : Negative * Negative = Positive
        # 2. So we need to keep track of minimum values also, as they can yield maximum values.
        
        global_max = prev_max = prev_min = nums[0]
        for num in nums[1:]:
            curr_min = min(prev_max*num, prev_min*num, num)
            curr_max = max(prev_max*num, prev_min*num, num)
            global_max= max(global_max, curr_max)
            prev_max = curr_max
            prev_min = curr_min
        return global_max

global_max: 모든 경우에서의 최댓값
prev_max: 이전까지의 최댓값
prev_min: 이전까지의 최솟값 => 음수 처리용인듯

모두 nums[0] 으로 초기화하고
nums[1] 부터 반복문 돌려서

현재 최댓값과 최솟값 구해주기
curr_min = min(prev_max*num, prev_min*num, num)
curr_max = max(prev_max*num, prev_min*num, num)
prev_min 은 음수이다가 양수가 되는 순간 max 의 후보가 됨

전체 최댓값 구하기

현재 최댓값과 최솟값은 prev 로 넘기기