Study Log

20200408 알고리즘

1. 두 수의 합

정수를 담은 배열과 목표 값이 주어질 때 더해서 목표값이 되는 index를 리턴하는 문제 (중복x)

Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for i, v in enumerate(nums):
            n = target - v
            if n in hash:
                return [hash[n], i]
            hash[v] = i
        return list()
  • Brute force는 시간복잡도가 높다 => 이 문제의 경우 hash로 n 만에 해결 가능

2. Reverse Integer

-2^31 <= integer <= 2^31-1

Solution

class Solution:
    def reverse(self, x: int) -> int:
        flag = False
        if x < 0:
            flag = True
            x *= -1
        res = 0
        while x > 0:
            res = res*10 + x%10
            x //= 10
            
        if flag:
            res *= -1
        if -2**31 > res or res > 2**31-1:
            return 0
        return res

3. Palindrome Number

정수가 회문 문자열인지 체크 ( 음수 포함 )

Solution

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        else:
            a = list()
            while x > 0:
                a.append(x%10)
                x //= 10
            
            for i in range(len(a) // 2):
                if a[i] != a[-1-i]:
                    return False
            return True

4. Roman to Integer

로마숫자 -> 정수로 변환

Solution

class Solution:
    def romanToInt(self, s: str) -> int:
        stack = list(str)
        res = 0
        while stack:
            s = stack.pop()
            if s == 'M':
                if stack[-1] == 'C':
                    stack.pop()
                    res += 900
                else:
                    res += 1000
            elif s == 'D':
                if stack[-1] == 'C':
                    stack.pop()
                    res += 400
                else:
                    res += 500
            elif s == 'C':
                if stack[-1] == 'X':
                    stack.pop()
                    res += 90
                else:
                    res += 100
            elif s == 'L':
                if stack[-1] == 'X':
                    stack.pop()
                    res += 40
                else:
                    res += 50
            elif s == 'X':
                if stack[-1] == 'I':
                    stack.pop()
                    res += 9
                else:
                    res += 10
            elif s == 'V':
                if stack[-1] == 'I':
                    stack.pop()
                    res += 4
                else:
                    res += 5
            else:
                res += 1
        return res

5. Longest Common Prefix

example Input: ['abc', 'abcd', 'ab']

Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return "" 
        minLength = 2147000000
        for v in strs:
            if len(v) < minLength:
                minLength = len(v)
        s = 0
        e = minLength 
        res = 0 
        while s <= e:
            mid = (s+e) // 2 
            if all([strs[0][:mid] == strs[k][:mid] for k in range(1, len(strs))]):
                res = mid
                s = mid + 1
            else:
                e = mid - 1
        return strs[0][:res]
Written by@[HongDongUk]
공부한 것을 소소하게 적는 블로그.

GitHubFacebook