class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
ans = []
heap = []
for i in range(2, len(nums)+1):
x = list(combinations(nums, i))
for y in x:
if list(y) == sorted(y):
heappush(heap, list(y))
while heap:
z = heappop(heap)
if len(ans) == 0 or ans[-1] != z:
ans.append(z)
return ans
사실 백트래킹을 하건 나처럼 itertools의 combinations (c++에선 next_permutation)을 쓰건
그냥 조건을 만족하는 애를 뽑아서 구하는건 쉬운데 중복을 없애는 것도 문제다.
(물론 이게 안 쉬울 수도 있다.. 백트래킹은 처음 배울 땐 어려우니까... 그럼 다른 문제로 연습하자)
파이썬에서 리스트는 hashable하지 않기 때문에 중복을 없애는 젤 쉬운 방법인 list -> set -> list는 불가능
그래서 두 가지의 방법을 생각할 수 있다.
1. heap에 넣을 때 tuple로 넣고 list -> set -> list로 바꾸고 tuple을 list로 다시 바꿈 (361ms)
2. heap에 heappush로 넣고 빼면서 중복 제거 (409ms)
위의 풀이는 처음 푼 2번 풀이고, 조금이나마 시간 비교를 해보고 싶어서 짠 1번 풀이는 아래와 같다.
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
ans = []
heap = []
for i in range(2, len(nums)+1):
x = list(combinations(nums, i))
for y in x:
if list(y) == sorted(y):
heap.append(y)
for top in list(set(heap)):
ans.append([*top])
return ans
leetcode의 경우 돌릴 때마다 수십ms의 차이가 난다. 즉 N<=2^15 ~ 32768 정도에선 별 차이 없다는거
1번은 heap이 heapq일 필요가 없고 속도가 더 빠르고 로직이 단순하다.
2번은 문제가 정렬된 순서를 요구할 때 사용하기 좋다.
2023.01.21 01:31:30
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.