본문 바로가기

전체 글50

leetcode 287. Find the Duplicate Number 풀이 문제 : n+1 길이의 [1, n] 사이의 정수를 포함하는 list에서 중복되는 숫자 하나를 반환하라 (하나만 존재함) Follow up : 1. Nums를 변환하지 말 것 2. O(1) 만큼의 메모리만 사용하여 해결할 것 3. O(n^2) 이하의 시간 복잡도를 가질 아이디어 : Follow up을 모두 충족하는 풀이를 생각했지만 어려웠다. 다른 사람의 코드를 보고 이해한 내용을 아래에 기술할 것이다. 코드 : class Solution: def findDuplicate(self, nums: List[int]) -> int: d = dict() for num in nums: if num in d: d[num] += 1 else: d[num] = 1 for key in d: if d[key] > 1: re.. 2021. 4. 1.
2021.4.1 새로운 달의 시작 벌써 3월 한달이 지나가고 새로운 한달의 시작이다.벚꽃도 피고 완연한 봄이다.웅크리지말고 밖으로 나가서 활동을 하고 에너지를 얻고새로운 경험을 많이 하는 한달이 되었으면 좋겠다. 2021. 4. 1.
leetcode 448. Find All Numbers Disappeared in an Array 풀이 문제: 길이가 n이고 [1, n] 사이의 숫자를 포함하는 list에서 [1, n] 사이에서 빠진 숫자를 모두 포함하는 list를 반환하라 follow up : 반환하는 list를 제외하고 추가적인 메모리를 사용하지 않으면서 O(n)의 시간 복잡도를 가지는 알고리즘을 구현해보자. 아이디어: input [1,1,2] output [3], input[1,1,1,2] output [3,4]와 같이 중복된 숫자를 제외하면 어떤 종류의 숫자가 있는지 파악 가능하다. set를 이용하여 차집합을 구한다. 코드: class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: snum = set(nums) ans = set(range(1,le.. 2021. 3. 31.
leetcode 169. Majority Element 풀이 문제 : 크기가 N 인 list에서 N/2 이상 등장하는 원소를 반환하라 아이디어: 각 원소의 갯수 dictionary 에 저장해서 major한 값을 찾는다. 코드 : class Solution: def majorityElement(self, nums: List[int]) -> int: ans = -1 d = dict() for n in nums: if n in d: d[n] += 1 else: d[n] = 1 for key in d: if d[key] > (len(nums)//2): ans = key return ans 파이썬에서는 dictionary 라는 해시테이블 자료형을 제공한다 key 와 value를 어떻게 순회하는지 익혀두면 매우 유용하다. 출처 : leetcode.com/problems/ma.. 2021. 3. 31.

티스토리툴바