파이썬에서 사전식으로 가장 작은 k 크기의 부분열을 찾는 프로그램

nums라고 하는 숫자 목록과 또 다른 값 k가 있다고 가정하면 사전순으로 크기가 k인 가장 작은 부분 수열을 찾아야 합니다.

따라서 입력이 nums =[2, 3, 1, 10, 3, 4] k =3과 같으면 출력은 [1, 3, 4]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• l :=숫자의 크기, r :=k - 1
• out :=새 목록
• 0~k 범위의 j에 대해
  • mn :=nums[r의 보수]
  • r에서 l 사이의 i에 대해 다음을 수행합니다.
    • mn>=nums[i의 보수]이면
      • mn :=nums[i의 보수]
      • 나는 :=나는
  • r :=r - 1
• 끝에 mn 삽입
• 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, nums, k):
      l, r = len(nums), k - 1
      out = []
      for j in range(k):
         mn = nums[~r]
         for i in range(r, l):
            if mn >= nums[~i]:
               mn = nums[~i]
               l = i
         r -= 1
         out.append(mn)
   return out
ob = Solution()
nums = [2, 3, 1, 10, 3, 4]
k = 3
print(ob.solve(nums, k))

입력

[2, 3, 1, 10, 3, 4], 3

출력

[1, 3, 4]