2021-01-21] Find the Most Competitive Subsequence

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3611/

Explore - LeetCode

 

문제의 난이도는 Medium인데 나에겐 왤케 어려운지.. 문제를 풀려고만 하지말고, 알고리즘 공부를 해야할 것 같다..

 

문제 에시를 보면 List와 k값이 주어지는데 원소가 k개인 부분시퀀스를 구하고 그중 가장 작은 것을 반환하는 것이다.

 

가능한 subsequence를 다 구한뒤 가장 작은 것을 반환하는 것이였다.

 

data = list(itertools.combinations(nums[nums.index(minval):],k))
return sorted(data)[0]
# data에는 k개의 원소를 가지는 부분시퀀스가 구해진다. 이를 sort하고 첫번째 값을 반환하면 된다!

역시나 세상은 호락호락하지 않다.. combinations을 구하는 함수는 너무 많이 시간을 잡아먹어 다른 방법을 고민한다.

 

가장 작은 값의 인덱스부터 찾아가 남은 원소가 k와 같으면 이게 우리가 원하는 답일 수 있다. ( 예제 1번은 해결된다! )

 

clist=nums
minval=min(nums)
minindex=nums.index(minval)
if len(clist)-minindex > k: # k보다 크면 그 안에 답을 만들 수 있음.
    ans.append(minval)
    k-=1
    clist=clist[minindex+1:] # 최소값보다 뒤의 부분 list를 생성
    minval=min(clist) # 변경된 list에서 최소값
elif len(clist)-minindex < k: # k가 크면 그 반대편의 부분list에서 최소값을 새로 찾아야함.
    minval=min(clist[:minindex]) 
else:
    ans.extend(clist[minindex:]) # k와 같으면 값 반환
    break

 

12개에서 85개까지 비약적인 발전은 했지만, 역시나 Time Limit에 걸리는 것을 보면, 너무 많이 min값을 찾는 것 같다.

python 이라도 탐색에 시간은 걸릴 수 밖에 없으니, 다른 방법을 생각해봐야 할 것 같다.

 

필자는 결국 스스로 생각은 못해냈다.. 이미 저기까지 간 것도 힘들었다.. 이 후의 문제풀이는 아래 링크를 참고했다.

 

www.youtube.com/watch?v=F1slBN7wFrI 

문제풀이)

 

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack=[]
        for i in range(len(nums)):
            #print(stack,len(stack)-1+len(nums)-i,k)
            while stack and nums[i]<stack[-1] and len(stack)-1+len(nums)-i>=k:
                stack.pop()
            if len(stack) < k:
                stack.append(nums[i])
        return stack
        """
        if k == len(nums):
            return nums
        ans=[]
        clist=nums
        minlist=sorted(nums)
        if clist==minlist:
            return clist[:k]
        #if len(minlist)==1:
        #    return clist[:k]
        #print(minlist, clist)
        minval=minlist[0]
        while k!=0:
            minindex=clist.index(minval)
            #print(minval, clist, len(clist) ,minindex,k)
            if len(clist)-minindex > k:
                ans.append(minval)
                k-=1
                clist=clist[minindex+1:]
                minval=min(clist)
            elif len(clist)-minindex < k:
                minval=min(clist[:minindex])
            else:
                ans.extend(clist[minindex:])
                break
        print(ans)
        return ans
        """