491. Non-decreasing Subsequences

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

개발뉴비

2023.01.21 01:31:30

조회 54 추천 0 댓글 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):
                    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번은 문제가 정렬된 순서를 요구할 때 사용하기 좋다.

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

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

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
86	909. Snakes and Ladders [1]	개발뉴비	23.01.24	52	0
85	909. Snakes and Ladders	이벤트ㅇㅅㅇ(219.251)	23.01.24	47	0
83	997. Find the Town Judge	이벤트ㅇㅅㅇ(219.251)	23.01.23	44	0
82	997. Find the Town Judge [1]	개발뉴비	23.01.23	73	0
81	백준 9996번	키비	23.01.23	55	0
78	마갤 입문함 [2]	키비	23.01.22	58	0
77	131. Palindrome Partitioning [1]	개발뉴비	23.01.22	55	0
75	93. Restore IP Addresses [1]	개발뉴비	23.01.21	69	0
74	Longest Palindromic Substring 5번	o오어o(14.37)	23.01.21	28	0
73	Restore IP Addresses 93번	o오어o(14.37)	23.01.21	38	0
72	안녕하세요 오늘부터 릿코 달리게씁니당 [2]	조르디(112.170)	23.01.21	52	0
	491. Non-decreasing Subsequences [1]	개발뉴비	23.01.21	54	0
70	974. Subarray Sums Divisible by K [1]	개발뉴비	23.01.19	42	0
69	926. Flip String to Monotone Increasing [1]	개발뉴비	23.01.17	39	0
68	57. Insert Interval [1]	개발뉴비	23.01.17	35	0
66	트리 문제 두 개 개빡치네;	개발뉴비	23.01.15	47	0
65	1061. Lexicographically Smallest ~	개발뉴비	23.01.15	39	0
64	여기 갤럼들은 전부 해외취업 준비중? [2]	EvenAsura	23.01.14	104	0
63	1519. Number of Nodes in the Sub-Tree~	개발뉴비	23.01.12	28	0
62	1443. Minimum Time to Collect All Apples	개발뉴비	23.01.11	40	0
59	230111 데일리	꽃지	23.01.11	67	0
58	100. Same Tree	개발뉴비	23.01.10	33	0
56	220110 데일리	꽃지	23.01.10	38	0
53	144. Binary Tree Preorder Traversal	개발뉴비	23.01.09	39	0
52	230109 데일리	꽃지	23.01.09	30	0
51	리트코드 4번 [4]	o오어o(222.121)	23.01.09	63	0
50	리트코드 3번	o오어o(222.121)	23.01.09	25	0
49	220108 데일리	꽃지	23.01.08	53	0
48	68. Text Justification	ㅇㅇ(12.50)	23.01.08	34	0
47	3번문제 코드 딱 한줄만 알려준다	ㅇㅇ(218.234)	23.01.08	36	0
46	코딩 테스트 tdd로 하시는 분 [1]	TS(119.64)	23.01.07	60	0
45	가스스테이션(데일리)	o오어o(222.121)	23.01.07	50	0
44	230107 데일리 [1]	꽃지	23.01.07	55	0
43	134. Gas Station	개발뉴비	23.01.07	47	0
42	1833. Maximum Ice Cream Bars	개발뉴비	23.01.06	56	0
41	230106 데일리	꽃지	23.01.06	49	0
38	오늘의 릿코드 Minimum Number of Arrows~	개발뉴비	23.01.05	40	0
36	230105 데일리 [3]	꽃지	23.01.05	63	0
35	2244. Minimum Rounds 이거 푸는데	TS(119.64)	23.01.05	36	0
34	데일리 문제 어떻게 알아봄...? [1]	TS(119.64)	23.01.05	38	0
33	230104 데일리 [2]	꽃지	23.01.04	85	0
31	Minimum Rounds to Complete All Task [1]	개발뉴비	23.01.04	101	0
30	944. Delete Columns to Make Sorted in TS	ㅇㅇ(119.64)	23.01.04	42	0
29	백준 17726 Inheritance	꽃지	23.01.04	57	0
28	백준 14503번 로봇 청소기	개발뉴비	23.01.04	93	0
23	오늘의 릿코드 Delete Columns to Make Sorted [2]	개발뉴비	23.01.03	78	0
22	오늘의 데일리 [3]	꽃지	23.01.03	82	0
19	리트코드 해보면서 느낀 점	ㅇㅇ(119.64)	23.01.03	90	0
18	어쨌든 TS로 대문자 판별하기 문제 풀었는데	ㅇㅇ(119.64)	23.01.03	46	0
17	저는 js로 할게요 [5]	ㅇㅇ(119.64)	23.01.03	78	0