491. Non-decreasing Subsequences

개발뉴비 · 2023-01-21T01:31:30+09:00

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 ansleetcode의 경우 돌릴 때마다 수십ms의 차이가 난다. 즉 N<=2^15 ~ 32768 정도에선 별 차이 없다는거1번은 heap이 heapq일 필요가 없고 속도가 더 빠르고 로직이 단순하다. 2번은 문제가 정렬된 순서를 요구할 때 사용하기 좋다.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

개발뉴비

2023.01.21 01:31:30

조회 56 추천 0 댓글 1

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
333	3355. Zero Array Transformation I	흑화뉴비	05.20	49	0
332	2918. Minimum Equal Sum of Two Arrays Af	흑화뉴비	05.10	21	0
331	2033. Minimum Operations to Make a Uni-V	흑화뉴비	03.28	44	0
330	2401. Longest Nice Subarray	흑화뉴비	03.19	37	0
329	1079. Letter Tile Possibilities	흑화뉴비	02.18	44	0
328	1718. Construct the Lexicographically La	흑화뉴비	02.16	26	0
327	1910. Remove All Occurrences of a Substr	흑화뉴비	02.11	28	0
326	2381. Shifting Letters II	흑화뉴비	01.05	42	0
323	2471. Minimum Number of Operations to So	흑화뉴비	24.12.25	29	0
322	773. Sliding Puzzle	흑화뉴비	24.11.27	30	0
321	3243. Shortest Distance After Road Addit	흑화뉴비	24.11.27	23	0
320	1233. Remove Sub-Folders from the Filesy	흑화뉴비	24.10.29	28	0
319	2684. Maximum Number of Moves in a Grid	흑화뉴비	24.10.29	28	0
318	2501. Longest Square Streak in an Array	흑화뉴비	24.10.29	41	0
317	3043. Find the Length of the Longest Com	흑화뉴비	24.09.24	38	0
316	1514. Path with Maximum Probability	흑화뉴비	24.08.27	37	0
315	264. Ugly Number II	흑화뉴비	24.08.19	32	0
314	2285. Maximum Total Importance of Roads	흑화뉴비	24.06.28	46	0
313	1552. Magnetic Force Between Two Balls	흑화뉴비	24.06.20	36	0
312	1482. Minimum Number of Days to Make m B	흑화뉴비	24.06.19	40	0
311	523. Continuous Subarray Sum	흑화뉴비	24.06.09	41	0
310	리트코드 갤러리 5월 이벤트 우승자 공지 [1]	진척	24.06.08	63	0
309	1208. Get Equal Substrings Within Budget	흑화뉴비	24.05.28	38	0
308	1608. Special Array With X Elements Grea	흑화뉴비	24.05.28	30	0
307	552. Student Attendance Record II	흑화뉴비	24.05.28	31	0
306	2597. The Number of Beautiful Subsets [1]	흑화뉴비	24.05.24	54	0
305	78. Subsets	흑화뉴비	24.05.21	30	0
304	1863. Sum of All Subset XOR Totals	흑화뉴비	24.05.21	35	0
302	1325. Delete Leaves With a Given Value	흑화뉴비	24.05.18	35	0
301	2331. Evaluate Boolean Binary Tree	흑화뉴비	24.05.18	26	0
298	3075. Maximize Happiness of Selected Chi	흑화뉴비	24.05.12	22	0
297	786. K-th Smallest Prime Fraction	흑화뉴비	24.05.12	28	0
296	506. Relative Ranks	흑화뉴비	24.05.08	37	0
295	2816. Double a Number Represented as a L	흑화뉴비	24.05.08	23	0
294	2487. Remove Nodes From Linked List	흑화뉴비	24.05.06	24	0
293	79. Word Search	o오어o(14.37)	24.05.04	27	0
292	45. Jump Game II	o오어o(14.37)	24.05.04	32	0
291	881. Boats to Save People	o오어o(14.37)	24.05.04	28	0
290	2441. Largest Positive Integer That Exis	흑화뉴비	24.05.02	26	0
289	2997. Minimum Number of Operations to Ma	흑화뉴비	24.05.01	24	0
288	2000. Reverse Prefix of Word	흑화뉴비	24.05.01	34	0
287	리트코드 갤러리 5월 이벤트 공지 [3]	진척	24.04.28	96	0
282	백준 1260. DFS와 BFS	차근차근춘식이(211.234)	24.04.23	45	0
277	206. Reverse Linked List	흑화뉴비	24.03.21	46	0
276	1669. Merge In Between Linked Lists	흑화뉴비	24.03.20	28	0
275	57. Insert Interval	흑화뉴비	24.03.18	29	0
274	2485. Find the Pivot Integer	흑화뉴비	24.03.13	24	0
273	1750. Minimum Length of String After Del	흑화뉴비	24.03.06	25	0
272	451. Sort Characters By Frequency	흑화뉴비	24.02.07	39	0
271	49. Group Anagrams	흑화뉴비	24.02.06	32	0