IT/Algorithm(29)
-
Leetcode 316. Remove Duplicate Letters - Python
Leetcode 316 문제 보기 문제 이해하기 소문자 알파벳으로 이루어진 문자열 s가 있다. (1 str: counter = collections.Counter(s) visited, stack = set(), [] for char in s: counter[char] -= 1 if char in visited: continue while stack and char 0: visited.remove(stack.pop()) stack.append(char) visited.add(char) return ''.join(stack) Leetcode 316. Remove Duplicate Letters https://leetcode.com/proble..
2022.05.07 -
Leetcode 819. Most Common Word - Python
Leetcode 819 문제 보기 문제 이해하기 문장 paragraph가 주어졌을 때, banned에 적힌 단어들을 제외하고 가장 많이 나타나는 단어를 찾아라. 정답 단어는 소문자로 출력하라. 아이디어 구상 문제에서 문장에 포함가능한 문장부호들이 주어졌다. 공백 포함 !?',;. 기호가 포함가능하다고 한다. 때문에 위 기호들을 제거하고 문장을 소문자로 치환한 후, 단어별로 쪼갠 후 banned의 단어들을 제외해준다면 가장 많이 출현하는 단어를 찾을 수 있을 것이다. 그러나 여기서는 좀 더 간명한 풀이 방법을 사용해보자. 바로 정규표현식을 이용한 방법이다. 정규표현식은 문자열을 편리하게 다룰 수 있게 하는 방법이다. 특정한 조건의 문자를 검색하거나 치환하는 과정을 매우 간편하게 처리할 수 있도록 돕는다. ..
2022.05.04 -
Leetcode 15. 3Sum - Python
Leetcode 15 문제 보기 문제 이해하기 정수가 담긴 리스트 nums가 있다. (-10^5 0: right -= 1 elif three_sum List[List[int]]: res = [] if len(nums) 0 and n..
2022.04.06 -
Leetcode 238. Product of Array Except Self - Python
Leetcode 238 문제 보기 문제 이해하기 -30이상 30이하의 수로 이루어진 리스트 nums가 있다. 이때 각 숫자당, 본인을 제외한 나머지 숫자들의 곱을 가지는 리스트를 출력하라. 예를 들어 nums = [1,2,3,4]일 경우, [(2 * 3 * 4), (1 * 3 * 4), (1 * 2 * 4), (1 * 2 * 3)], 즉 [24,12,8,6]를 출력하면된다. 다만 나눗셈을 사용해서는 안되며 O(n) 이내의 시간복잡도를 가져야한다. 아이디어 구상 보통의 경우라면, nums의 모든 숫자를 곱한 값에서 각 원소를 나누면 답이 쉽고 빠르게 나올 것이다. 그러나 본 문제에서는 나눗셈을 사용해서는 안된다. 그렇다면 어떻게 해결해야할까? 시각화를 통해 생각을 정리해보자. (nums = [1,2,3,4..
2022.04.04 -
Leetcode 90. Subsets II - Python
Leetcode 90 문제 보기 문제 이해하기 주어진 nums는 중복된 원소가 존재가능한 숫자들의 리스트다. nums에서 얻을 수 있는 부분집합들을 구하되, 부분집합들은 중복되어선 안된다. 이 때 출력 순서는 상관없다. 아이디어 구상 가장 먼저 떠오른 생각은, 우선 조합을 모두 구한 후 set을 취해 중복을 제거하는 방법이다. nums의 길이가 최대 10까지 가능한만큼, 심플하면서도 성능도 나쁘지 않을 것이다. 하지만 학습의 목적을 위해 조금 다른 방법도 생각해보자. 본 문제는 LeetCode 40번과 거의 유사한 문제다. LeetCode 40번 보기 마찬가지로 중복되는 조합을 제외해야하므로 약간의 트릭이 필요하다. 하나의 원소를 포함시키는 경우와, 그 원소와 같은 값의 원소들은 전부 제외시키는 경우, ..
2022.03.31 -
Leetcode 332. Reconstruct Itinerary - Python
Leetcode 332 문제 보기 문제 이해하기 비행기 표 리스트 tickets가 주어졌다. tickets의 각 원소는 하나의 표를 의미하며, [출발지, 도착지]로 구성된다. JFK에서 출발하는 가능한 여행 경로 중, 사전순(lexical order)으로 방문하는 단 하나의 경로를 구하여라. 아이디어 구상 사전순으로 방문해야하므로, 리스트를 value로 하는 딕셔너리 형태로 그래프를 구성하되 각각의 key가 정렬된 value를 가지도록 하면 되겠다. 이후, 해당 그래프에서 JFK에서 시작하여 하나씩 value를 꺼내면 정답을 구할 수 있을 것이다. 이 때 약간의 트릭을 더 추가해 최적화를 해보자. 각각의 value들을 사전순으로 정렬하면, 값을 꺼낼 때 pop(0)로 해야한다. 그러나 이는 O(n)의 시..
2022.03.30