[leetcode] 5, 8, 13, 14

13. Roman to Integer

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

My Answer 1: Accepted (Runtime: 48 ms - 67.36% / Memory Usage: 14.3 MB - 58.40%)

class Solution:
    def romanToInt(self, s: str) -> int:
        symbols = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        subtract = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
        
        ans = 0
        i = 0
        while i < len(s):
            if s[i:i+2] in subtract:
                ans += subtract[s[i:i+2]]
                i += 1
            else:
                ans += symbols[s[i]]
            i += 1
            
        return ans

딕셔너리에 symbol 정리, subtract 에 해당하는 symbol 들도 정리

연속된 두 문자가 subtract 에 포함되면 subtract 값으로 계산
아니면 원래 symbol 값으로 계산

---

14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/

My Answer 1: Accepted (Runtime: 36 ms - 58.69% / Memory Usage: 14.3 MB - 81.36%)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]
        
        prefix = ""
        for i in range(1, len(strs[0])+1):
            cnt = 0
            for j in range(1, len(strs)):
                if strs[0][:i] != strs[j][:i]:
                    break
                cnt += 1
            if cnt == len(strs)-1:
                prefix = strs[0][:i] if len(prefix) < len(strs[0][:i]) else prefix
            else:
                break
        
        return prefix
                

처음에는 모든 스트링에 공통되는 substring 을 구하는줄 알고 시간을 좀 뺏김..ㅎ
prefix... 접두사... 제대로 볼 것!!!!!!

strs[0] 을 기준으로 다른 스트링도 같은 접두사를 가지는지 확인
모두 가지면 prefix update

그냥 zip() 으로 모든 문자열 한번에 비교해도 됐을듯..

---

5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

My Answer 1: Time Limit Exceeded (159 / 177 test cases passed.)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                p = s[i:j]
                if p == p[::-1]:
                    ans = p if len(ans) < len(p) else ans
        
        return ans

지금 보고 있는 substring 이 reverse 한 값과 같으면 ans update

이거 4 번째 만나는건데... 4 전 4 패 문제...ㅠ
이번엔 무조건 제대로 알아두기!!!

Solution 1: Accepted (Runtime: 4340 ms - 29.66% / Memory Usage: 21.9 MB - 17.85%)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        # Form a bottom-up dp 2d array
        # dp[i][j] will be 'true' if the string from index i to j is a palindrome. 
        dp = [[False] * n  for _ in range(n)]
        
        ans = ''
        # every string with one character is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
            
        maxLen = 1
        for start in range(n-1, -1, -1):
            for end in range(start+1, n):             
                # palindrome condition
                if s[start] == s[end]:
                    # if it's a two char. string or if the remaining string is a palindrome too
                    if end - start == 1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if maxLen < end - start + 1:
                            maxLen = end - start + 1
                            ans = s[start: end+ 1]
        
        return ans

DP 를 써야했다...

모든 s 마다 자기 자신 한 글자는 palindrome 이 되니까 dp[i][i] = True 설정

start 는 맨 뒤에서부터 시작하고, end 는 start 의 오른쪽을 쭉 훑어줌

start 값과 end 값이 같고 그 사이의 값들도 palindrome 이면
(=> if end - start == 1 start, end 딱 두글자만 / or dp[start+1][end-1]: 두글자 이상 있을 때)

dp = True & maxLen 기반으로 ans update

---

8. String to Integer (atoi)

https://leetcode.com/problems/string-to-integer-atoi/

My Answer 1: Accepted (Runtime: 24 ms - 98.70% / Memory Usage: 14.2 MB - 56.83%)

class Solution:
    def myAtoi(self, s: str) -> int:
        s = s.lstrip(" ")
        if len(s) == 0:
            return 0
        
        np = ""
        negative = 0
        ans = 0
        if s[0] == "-" or s[0] == "+" or s[0].isdigit():
            for i in range(len(s)):
                if i == 0 and s[i] == "-":
                    negative = 1
                elif i == 0 and s[i] == "+":
                    continue
                elif s[i].isdigit():
                    ans *= 10
                    ans += int(s[i])
                else:
                    break
        else:
            return 0
        
        if negative:
            ans *= -1
        
        if ans < -2 ** 31:
            return -2 ** 31
        if ans > 2 ** 31 - 1:
            return 2 ** 31 - 1
        return ans

따져야할 조건이 넘 많아서 짜증났던...

우선 앞쪽의 공백들 제거 => s.lstrip(" ")

시작 값이 +, -, 숫자가 아니면 return 0

0 부터 보면서 시작값이 부호일 때 처리
숫자는 ans 에 10 곱해가면서 계속 더해주기
중간에 문자, 부호들이 나오면 break

음수 처리 & 범위 체크 하고 return ans