Leetcode 90 문제 보기 문제 이해하기 주어진 nums는 중복된 원소가 존재가능한 숫자들의 리스트다. nums에서 얻을 수 있는 부분집합들을 구하되, 부분집합들은 중복되어선 안된다. 이 때 출력 순서는 상관없다. 아이디어 구상 가장 먼저 떠오른 생각은, 우선 조합을 모두 구한 후 set을 취해 중복을 제거하는 방법이다. nums의 길이가 최대 10까지 가능한만큼, 심플하면서도 성능도 나쁘지 않을 것이다. 하지만 학습의 목적을 위해 조금 다른 방법도 생각해보자. 본 문제는 LeetCode 40번과 거의 유사한 문제다. LeetCode 40번 보기 마찬가지로 중복되는 조합을 제외해야하므로 약간의 트릭이 필요하다. 하나의 원소를 포함시키는 경우와, 그 원소와 같은 값의 원소들은 전부 제외시키는 경우, ..

Leetcode 332 문제 보기 문제 이해하기 비행기 표 리스트 tickets가 주어졌다. tickets의 각 원소는 하나의 표를 의미하며, [출발지, 도착지]로 구성된다. JFK에서 출발하는 가능한 여행 경로 중, 사전순(lexical order)으로 방문하는 단 하나의 경로를 구하여라. 아이디어 구상 사전순으로 방문해야하므로, 리스트를 value로 하는 딕셔너리 형태로 그래프를 구성하되 각각의 key가 정렬된 value를 가지도록 하면 되겠다. 이후, 해당 그래프에서 JFK에서 시작하여 하나씩 value를 꺼내면 정답을 구할 수 있을 것이다. 이 때 약간의 트릭을 더 추가해 최적화를 해보자. 각각의 value들을 사전순으로 정렬하면, 값을 꺼낼 때 pop(0)로 해야한다. 그러나 이는 O(n)의 시..

Leetcode 93 문제 보기 문제 이해하기 일련의 숫자 s가 주어진다. (1 1) or int(digit) > 255): return cur.append(digit) dfs(i + 1, dots - 1) cur.pop() dfs(0, 4) return res Leetcode 93. Restore IP Addresses https://leetcode.com/problems/restore-ip-addresses/​ ​ -문제해결흐름을 간단히 정리한 주관적 포스팅- -부족한 설명이 있다면 부디 조언 부탁드립니다- 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다

Leetcode 1980 문제 보기 문제 이해하기 각각의 길이가 n인 n개의 이진수 문자열(binary string)들의 리스트인 nums가 있다. (1

Leetcode 40 문제 보기 문제 이해하기 1에서 50까지의 수로 이루어진 리스트 candidates가 있다. (1 target: last_idx = c break dfs()의 base case는 다음과 같다. target에서 값을 계속 빼나갈 때, 값이 0이 되는 순간 해당하는 조합을 res에 담고 return한다. if remain == 0: res.append(combi[:]) return dfs()의 재귀 부분은 다음과 같다. 아이디어 구상에서 살펴봤듯이, 탐색을 진행했던 원소와 동일한 값의 원소가 있을 경우, 그 원소의 탐색은 skip한다. 이 때, 이전 원소의 값을 보관하기 위한 변수 pre를 -1로 초기화한다. (candidates의 모든 원소는 1이상이기 때문) 탐색 시 remain <..

Leetcode 1849 문제 보기 문제 이해하기 0 ~ 9까지의 숫자로 이루어진 문자열 s를 2개 이상의 substring으로 나눠보자. 이 때 각 substring들이 바로 이전의 substring에 비해 1이 작은 수로 이루어져 있다면, 즉 "substring = previous_substring - 1"일 경우, true를 return하는 프로그램을 작성하라. 각각의 substring은 빈 문자열이서는 안되며, substring은 1개 이상, 20개 이하의 숫자로 이루어져있다. 또한 1 ~ 9 이전에 등장하는 "0"은 무시해도 된다. 즉, "05" 은 숫자 5다. 아이디어 구상 Decision Tree를 그리며 생각해보자. s = "050043"인 test case를 살펴보자. 적어도 한 번은 s..