Link Search Menu Expand Document

LeetCode Easy Python 언어 풀이

Table of contents

  1. 1. Two Sum
  2. 7. Reverse Integer
  3. 14. Longest Common Prefix
  4. 20. Valid Parentheses
  5. 35. Search Insert Position
  6. 38. Count and Say
  7. 53. Maximum Subarray
  8. 58. Length of Last Word
  9. 66. Plus One
  10. 136. Single Number
  11. 167. Two Sum II - Input array is sorted
  12. 169. Majority Element
  13. 204. Count Primes
  14. 217. Contains Duplicate
  15. 231. Power of Two
  16. 242. Valid Anagram
  17. 258. Add Digits
  18. 263. Ugly Number
  19. 268. Missing Number
  20. 278. First Bad Version
  21. 1678. Goal Parser Interpretation

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

xx 나누기 10의 몫 (1의 자리를 제외한 값) 을 대입한다.
음수 나누기를 위해 x를 정수로 변환한다.
resx 나누기 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 인지 확인해서 90 으로 바꾸고,
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

딕셔너리 dicnums 의 값을 키로 두고, 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의 제곱수 - 1and 연산의 결과는 항상 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

num2,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