Leetcode98 [LeetCode] Max Consecutive Ones 파이썬 (문자열 압축) class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: local_max = 0 tmp = 0 for i in nums: if i == 1: tmp += 1 else: # print(local_max, tmp) local_max = max(local_max, tmp) tmp = 0 else: local_max = max(local_max, tmp) return local_max 주의점: loop가 정상적으로 순회한 후에도 max값이 update가 안되어있을 수 있기 때문에 for-else문을 통해 update 시켜줘야 한다. 카카오 문자열 압축 문제에서도 나온 유의사항. 다른 풀이는 class Solution(object): d.. 2021. 4. 29. [LeetCode] License Key Formatting 파이썬 (str.replace) class Solution: def licenseKeyFormatting(self, s: str, k: int) -> str: tmp = [] s = s.replace("-","") s = s[::-1] for i in range(0,len(s),k): tmp.append(s[i:i+k]) # print(tmp) ans = "-".join([x[::-1] for x in tmp[::-1]]) return ans.upper() 조건 1. alphanumeric, dashes('-') 2. 정확히 k개의 char만큼씩 group으로 나누어야 함 2-1. 첫번째 group의 경우 1 2021. 4. 29. [LeetCode] Number Complement 파이썬 (format, bitwise) format() 함수를 사용해서 진법을 출력할때 앞의 str를 제거하고 출력할 수 있다. Format Specification Mini-Language 이런식으로 출력된다. print(format(num, 'b')) print(bin(num)) class Solution: def findComplement(self, num: int) -> int: com_bi = [str(abs(int(x)-1)) for x in str(format(num, 'b'))] return com_bi abs(int(x) - 1) 을 해줌으로써 1 -> 0 , 0 -> 1로 swap 해준다. 2021. 4. 19. [LeetCode] Island Perimeter 파이썬 (island, traverse) 풀이방법: 2-d array를 traverse하면서 (row col) land 일 경우 4를 더해준다. 단, land일 경우 land의 위쪽과 왼쪽일 경우 -2를 더해준다. 왼쪽과 위쪽만 체크하는 이유는 traverse의 방향 때문에 그렇다. 그림으로 설명 오른쪽 아래 land 기준으로 위의 land에서 한개, 오른쪽 아래 land에서 한개 겹치는 land가 있을 때마다 2개씩 빼줘야 한다. 여기서는 grid의 side length를 1로 주어졌기 때문에 그냥 2를 빼주면 된다. class Solution(object): def islandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ count, repeat = 0, 0 f.. 2021. 4. 19. [LeetCode] Hamming Distance 파이썬 (bitwise) class Solution(object): def hammingDistance(self, x, y): """ :type x: int :type y: int :rtype: int """ distance = 0 z = x ^ y while z: distance += 1 z &= z - 1 return distance def hammingDistance2(self, x, y): """ :type x: int :type y: int :rtype: int """ return bin(x ^ y).count('1') 2번째 솔루션 비트 XOR 연산으로 position이 서로 다른지 확인한다. x = 1, y = 4일 경우 001 XOR 100 = 101 이 str에서 count메서드를 사용해서 1의 횟수를 retur.. 2021. 4. 19. [LeetCode] Repeated Substring Pattern 파이썬 (KMP) 문제 풀이하기전에 KMP 알고리즘이 무엇인지 알아보자 이 문제를 Brute Force로 풀면 풀리긴 하지만. O(n*m)의 문제를 O(n)으로 풀 수 있는 KMP 알고리즘으로 풀어보자 알고리즘 자체는 어렵지 않지만 설명이 어쩔 수 없이 길어지는 알고리즘이다. 요약: LPS 라는 table을 생성 ( Longest Prefix and also Suffix ) LPS 테이블을 활용해서 이미 searched된 pattern은 skip. LPS 테이블에서 0이 아닌 sub-pattern부터 탐색 가능하기 때문에 효율적인 방식. class Solution(object): def repeatedSubstringPattern(self, str): """ :type str: str :rtype: bool """ def.. 2021. 4. 18. [LeetCode] Assign Cookies 파이썬 (greedy) class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() result, i = 0, 0 for j in range(len(s)): if i == len(g): break if s[j] >= g[i]: result += 1 i += 1 return result 우선 sort 하고 two pointer(i,j) i를 g의 pointer로 사용하고 j는 s의 pointer로 사용하면서 하나씩 체크해 나간다. i == len(g) 를 통해 g의 모든 element를 체크했으면 exit s의 j-th 원소와 g의 i-th 원소를 비교하면서 조건에 맞으면 result에 count + 1 i를 한.. 2021. 4. 17. [LeetCode] Find All Numbers Disappeared in an Array 파이썬(set.difference) class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: n = len(nums) nums1 = list(range(1,n+1)) return list(set(nums1).difference(nums)) 2021. 4. 16. [LeetCode] Arranging Coins 파이썬 (Binary Search, maximize) class Solution2(object): def arrangeCoins(self, n): """ :type n: int :rtype: int """ left, right = 1, n while left int: left, right = 0, n while left n: right = mid - 1 else: left = mid + 1 return right # need maximum value 문제를 직사각형으로 확장하면 쉽게 풀리지만 그걸 떠올리기가 쉬운지는 모르겠음. 높이(k)가 3일 경우, o x x o o x o o o 이런식으로 만들어 진다. 여기에 1열을 추가한다면 o x x x o o x x o o o x 이렇게 k * k+1의 직사각형의 면적의 절반이 n개의 코인을 위치시킬 수 있는 최.. 2021. 4. 16. 이전 1 2 3 4 ··· 11 다음
