➤ projectdiscovery➤ Remix➤ Rescript➤ Purescript➤ npm➤ Cloudflare➤ React➤ Next.js➤ GO➤ Hyper-V➤ Tibero➤ Git➤ Algorithms, 2020년

LeetCode easy, Python, 2020년

November 26, 2020

1. Two Sum

target 빼기 nums 값(n) 이 dic의 키값이면 dic의 value와 현재 n 의 인덱스를 return한다.
위의 if문을 충족하지 않는다면 dic의 키 = nums 값(n), 밸류 = n의 인덱스로 할당한다.

  • dic[n]=i 의 식을 if문 위에 위치시키면 nums = [3,3] 일 경우 [0,0] 이 return된다.
Runtime: 40 ms, faster than 97.03% of Python3 online submissions for Two Sum.
Memory Usage: 14.4 MB, less than 95.91% of Python3 online submissions for Two Sum.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, n in enumerate(nums):
            if target-n in dic:
                return [dic[target-n],i]
            dic[n]=i
        return

2020.11.26

7. Reverse Integer

x 에 x 나누기 10의 몫 (1의 자리를 제외한 값) 을 대입한다.
음수 나누기를 위해 x를 정수로 변환한다.
res 에 x 나누기 10의 나머지 (1의 자리) 와 res 곱하기 10 (기존 res 값의 1의 자리를 10의 자리로 올리기 위해) 을 더한 값을 대입한다.
32bit integer 라는 조건을 만족하기 위해 값의 범위를 확인한다.

  • int32 max = 2147483647, int32 min = -2147483648
  • 파이썬에서 음수 나눈 나머지 y=ax+b
class Solution:
    def reverse(self, x: int) -> int:
            res = 0
            xx = abs(x)
            while xx != 0:
                res, xx = (res * 10) + (xx % 10), xx // 10
                if res > 2147483647 or res < -2147483648:
                    return 0
            return res if x>0 else -res

2020.11.27

14. Longest Common Prefix

가장 길이가 짧은 단어(short)를 찾은 뒤 short 의 문자와 나머지 문자열들의 문자를 비교한다.
비교 중 같지 않은 문자가 나올 경우 이전의 통과한 문자들만 return 한다.

Runtime: 36 ms, faster than 45.02% of Python3 online submissions for Longest Common Prefix.
Memory Usage: 14.3 MB, less than 47.57% of Python3 online submissions for Longest Common Prefix.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        strs.sort(key=len)
        short = strs[0]
        for i, c in enumerate(short):
            for str in strs[1:]:
                if str[i] != c:
                    return short[:i]
        return short

2020.11.27

20. Valid Parentheses

s 의 길이가 홀수면 짝이 맞지 않으므로 return False 를 한다.
괄호의 짝을 딕셔너리에 저장하고, 스택을 만든다.
여는 괄호 는 스택에 push 하고, 닫는 괄호 일 경우 스택의 마지막 값과 매칭(딕셔너리 이용)이 될 경우 pop 한다.
이 과정에서 괄호가 매칭되지 않으면 순서가 잘못되었으므로 return False 를 한다.
만약 위의 모든 과정이 끝나고 스택에 남아있는 값이 있을 경우도 return False 를 한다.

Runtime: 24 ms, faster than 94.16% of Python3 online submissions for Valid Parentheses.
Memory Usage: 14.1 MB, less than 61.11% of Python3 online submissions for Valid Parentheses.

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2!=0:
            return False
        
        stack = list()

        dic = {'(':')','{':'}','[':']'}
        
        for i, c in enumerate(s):
            if s[i] in dic:
                stack.append(s[i])
            else:
                if len(stack)!=0 and dic[stack[-1]] == s[i]:
                    stack.pop()
                else:
                    return False
        if stack:
            return False
        else:
            return True

2020.12.03

35. Search Insert Position

Binary Search (이진탐색)을 이용한다.

Runtime: 36 ms, faster than 99.22% of Python3 online submissions for Search Insert Position.
Memory Usage: 15 MB, less than 9.31% of Python3 online submissions for Search Insert Position.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target == 0 or nums[0]==target:
            return 0
    
        low, high = 0, len(nums)
        
        while low<high:
            middle = (high+low)//2
            if nums[middle] < target:
                low = middle+1
            else :
                high = middle
                
        return low

2020.12.02

38. Count and Say

문자열의 n번째와 n+1을 비교해서 같으면 count 를 증가시키고,
다를 경우 count + 해당 문자 를 val 에 더하고, count 를 초기화한다.

Runtime: 40 ms, faster than 70.73% of Python3 online submissions for Count and Say.
Memory Usage: 14.4 MB, less than 26.69% of Python3 online submissions for Count and Say.

class Solution:
    def countAndSay(self, n: int) -> str:
        
        val = ""
        res = "1"
        
        for _ in range(n-1):
            cnt = 1
            for j in range(len(res)-1):
                if res[j]==res[j+1]:
                    cnt+=1
                else:
                    val += str(cnt) + res[j]
                    cnt = 1
            val += str(cnt)+res[-1]
            res = val
            val = ""
        return res

2020.12.07

53. Maximum Subarray

모든 인덱스의 최대 합계를 저장한다.

Runtime: 88 ms, faster than 7.10% of Python3 online submissions for Maximum Subarray.
Memory Usage: 15.1 MB, less than 5.01% of Python3 online submissions for Maximum Subarray.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i]=max(nums[i-1]+nums[i],nums[i])
        return max(nums)

2020.12.08

58. Length of Last Word

양 끝의 공백 을 제거하고, 공백 을 기준으로 배열을 만들어서 마지막 단어의 길이를 return 한다.

Runtime: 28 ms, faster than 72.44% of Python3 online submissions for Length of Last Word.
Memory Usage: 14.2 MB, less than 38.22% of Python3 online submissions for Length of Last Word.

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.strip().split(' ')[-1])

2020.12.08

66. Plus One

배열의 마지막 요소부터 9 인지 확인해서 9 는 0 으로 바꾸고,
9 가 아니라면 +1 을 해서 return 한다.

Runtime: 32 ms, faster than 58.79% of Python3 online submissions for Plus One.
Memory Usage: 14.3 MB, less than 11.90% of Python3 online submissions for Plus One.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        l = len(digits)
        i = 1
        
        while i<=l:
            if digits[-i]!=9:
                digits[-i]+=1;
                return digits
            else:
                digits[-i]=0
                i+=1
        return [1]+digits

2020.12.04

136. Single Number

방법 1

nums 를 오름차순으로 정렬한 뒤, 값을 2개씩 비교해가며 같은 경우 pop 한다.
nums 에 남은 마지막 값을 return 한다.

Runtime: 196 ms, faster than 16.13% of Python3 online submissions for Single Number.
Memory Usage: 15.8 MB, less than 99.91% of Python3 online submissions for Single Number.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        i = 1
        result = list()
        while i < len(nums):
            if nums[i-1]==nums[i]:
                nums.pop(i)
                nums.pop(i-1)
                i-=1
            i+=1
        return nums[0]

방법 2

bool 자료형을 기본으로 가지는 딕셔너리를 만든다.
nums 의 값을 key로 넣고, value는 자기 자신의 not 으로 대입한다.
딕셔너리 값이 True 인 키를 return 한다.

Runtime: 140 ms, faster than 26.70% of Python3 online submissions for Single Number.
Memory Usage: 16.5 MB, less than 88.19% of Python3 online submissions for Single Number.

from collections import defaultdict
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        l = defaultdict(bool)
        
        for i in nums:
            l[i] = not l[i]
            
        for i in l:
            if l[i]==True:
                return i

2020.12.04

167. Two Sum II - Input array is sorted

시작점 s 은 0부터 끝점 e 는 배열의 마지막 인덱스로 대입한 뒤,
target 보다 배열[s] + 배열[e] 이 크면 s 에 1을 더하고,
작으면 e 에 1을 빼며, 같으면 retrun 한다.

Runtime: 52 ms, faster than 98.27% of Python3 online submissions for Two Sum II - Input array is sorted.
Memory Usage: 14.8 MB, less than 10.13% of Python3 online submissions for Two Sum II - Input array is sorted.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        if len(numbers) == 2:
            return [1,2]
        
        s = 0
        e = len(numbers)-1
        res = 0
        while True:
            res = numbers[s]+numbers[e]
            if target == res:
                return [s+1,e+1]
            elif target < res:
                e-=1
            elif target > res:
                s+=1

2020.12.09

169. Majority Element

숫자 카운트를 세고, 가장 큰 value를 가진 key를 return 한다.

Runtime: 160 ms, faster than 72.93% of Python3 online submissions for Majority Element.
Memory Usage: 15.6 MB, less than 15.29% of Python3 online submissions for Majority Element.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = collections.Counter(nums)
        return max(dic, key=dic.__getitem__)

2020.12.08

204. Count Primes

에라토스테네스의 체 방법을 사용했다.

Runtime: 512 ms, faster than 65.95% of Python3 online submissions for Count Primes.
Memory Usage: 25.7 MB, less than 55.70% of Python3 online submissions for Count Primes.

class Solution:
    def countPrimes(self, n: int) -> int:
        
        if n<=2:return 0
        
        cnt = 0
        arr = [True] * n
        sqrt = int(n**0.5)+1
        
        for i in range(2, sqrt):
            if arr[i] is True:
                cnt+=1
                for j in range(i+i, n, i):
                    arr[j]=False
                    
        for i in range(sqrt, n):
            if arr[i] is True:
                cnt+=1

        return cnt

2020.12.09

217. Contains Duplicate

딕셔너리 dic 에 nums 의 값을 키로 두고, value를 1 씩 더한다.
이미 value가 1 인 경우에는 이미 한 번 더해진 경우가 있다는 의미이므로 return True 한다.

Runtime: 108 ms, faster than 93.76% of Python3 online submissions for Contains Duplicate.
Memory Usage: 21.4 MB, less than 10.10% of Python3 online submissions for Contains Duplicate.

from collections import defaultdict
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dic = defaultdict(int)
        
        for i in nums:
            if dic[i]==1:
                return True
            dic[i]+=1
        
        return False

2020.12.10

231. Power of Two

2의 제곱수 와 2의 제곱수 - 1 의 and 연산의 결과는 항상 0이다.

Runtime: 28 ms, faster than 83.36% of Python3 online submissions for Power of Two.
Memory Usage: 14 MB, less than 96.10% of Python3 online submissions for Power of Two.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return (n>0) and (n&(n-1)==0)

2020.12.11

242. Valid Anagram

방법 1

정렬 시켜서 같은 지 확인한다.

Runtime: 40 ms, faster than 84.57% of Python3 online submissions for Valid Anagram.
Memory Usage: 15 MB, less than 6.58% of Python3 online submissions for Valid Anagram.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

방법 2

딕셔너리에 문자열을 key 로 넣고, s의 문자열 key의 value에는 1을 더하고,
t의 문자열 key의 value는 1을 뺀다.
모든 key의 value 가 0 이면 true이고, 아니면 false이다.

Runtime: 44 ms, faster than 73.04% of Python3 online submissions for Valid Anagram.
Memory Usage: 14.4 MB, less than 47.12% of Python3 online submissions for Valid Anagram.

from collections import defaultdict
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s)!=len(t):
            return False
        dic = defaultdict(int)
        for i in range(len(s)):
            dic[s[i]]+=1
            dic[t[i]]-=1
        for key in dic:
            if dic[key]!=0:
                return False
        return True

2020.12.11

258. Add Digits

num을 10으로 나눈 나머지와 몫을 더한 값이 9 이하일 때 return 한다.

Runtime: 32 ms, faster than 61.16% of Python3 online submissions for Add Digits.
Memory Usage: 14.1 MB, less than 82.66% of Python3 online submissions for Add Digits.

class Solution:
    def addDigits(self, num: int) -> int:
        if num<10:return num
        
        while num>=10:
            num = num//10 + num%10
        return num

솔루션

  • 9는 9의 배수만 나눌 수 있다.
  • 10 = 9 + 1
  • 15 = 9 + 6
  • 30 = 9*3 + 3
Runtime: 28 ms, faster than 83.37% of Python3 online submissions for Add Digits.
Memory Usage: 14.3 MB, less than 18.60% of Python3 online submissions for Add Digits.

class Solution:
    def addDigits(self, num: int) -> int:
        return 1 + (num - 1) % 9 if num else 0

2020.12.11

263. Ugly Number

num 을 2,3,5 로 계속 나눈다.
num 이 1이 되면 2,3,5 로만 나눠진 것이므로 true를 반환하고,
num 이 1이 아니면서 2,3,5 로 나눌 수 없으면 false 를 반환한다.

Runtime: 32 ms, faster than 57.77% of Python3 online submissions for Ugly Number.
Memory Usage: 14.3 MB, less than 19.35% of Python3 online submissions for Ugly Number.

class Solution:
    def isUgly(self, num: int) -> bool:
        
        if num <= 0:
            return False
        
        while num!=1:
            if num%2==0:
                num=num//2
            elif num%3==0:
                num=num//3
            elif num%5==0:
                num=num//5
            else:
                return False
        return True

2020.12.14

268. Missing Number

nums 는 순차이므로 xor 연산을 이용해 남는 숫자를 찾는다.

Runtime: 136 ms, faster than 38.61% of Python3 online submissions for Missing Number.
Memory Usage: 15.5 MB, less than 27.11% of Python3 online submissions for Missing Number.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)
        for i in range(len(nums)):
            res ^= i^nums[i]
        return res

2020.12.14

278. First Bad Version

Binary Search (이진탐색)을 이용한다.

Runtime: 28 ms, faster than 70.84% of Python3 online submissions for First Bad Version.
Memory Usage: 14.2 MB, less than 46.53% of Python3 online submissions for First Bad Version.

class Solution:
    def firstBadVersion(self, n):
        low, high = 1, n
        
        while low<high:
            middle = low+(high-low)//2
            if isBadVersion(middle):
                high = middle
            else :
                low = middle+1
        return low

2020.12.14

1678. Goal Parser Interpretation

replace 함수를 이용한다.

Runtime: 32 ms, faster than 74.96% of Python3 online submissions for Goal Parser Interpretation.
Memory Usage: 14.3 MB, less than 42.09% of Python3 online submissions for Goal Parser Interpretation.

class Solution:
    def interpret(self, command: str) -> str:
        return command.replace("()","o").replace("(al)","al")

2020.12.11