[알고리즘]6번째 알고리즘 풀이

[seroak]

📝 Description

무엇을?

• 알고리즘 풀이

문제1

• https://leetcode.com/problems/filling-bookcase-shelves/description/

문제2

• https://leetcode.com/problems/search-in-rotated-sorted-array/description/

[seroak]

33. Search in Rotated Sorted Array

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        st = 0
        en = len(nums) - 1

        while st <= en:
            mid = (st + en) // 2

            # mid값이 찾고있는 target값과 같으면 mid값을 반환
            if nums[st] == target:
                break
            if st == mid == en:
                return -1
            # nums[st],nums[mid],nums[en]을 비교하면 2개 사이중 하나 이상은 순서대로 정렬되어있다
            # nums[st]가 nums[mid-1]보다 작다 즉 여기 사이가 순서대로 정렬되어 있다
            if nums[st] <= nums[mid]:
                # 순서대로 정렬되어 있는 쪽 사이에 target값이 들어갈 수 있다면
                if nums[st] <= target <= nums[mid]:
                    en = mid
                else:
                    st = mid + 1
            # nums[mid]가 nums[en]보다 작다 즉 여기 사이가 순서대로 정렬되어 있다
            else:
                if nums[mid] <= target <= nums[en]:
                    st = mid
                else:
                    en = mid - 1
        else:

            return -1
        return st

[seroak]

Filling Bookcase Shelves 시간초과

class Solution:

    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        answer = [2**63 - 1]
        def backTracking(booksIdx, curHeight, curWidth, shelfHeight):

            if booksIdx == len(books):
                answer[0] = min(answer[0], curHeight)

                return
            # 옆으로 쌓는 경우
            # 해당 층의 사용된 넓이 + 책의 넓이
            if curWidth + books[booksIdx][0] <= shelfWidth:

                # 책 idx를 1 증가 시키고 현재 높이와 옆으로 둘 책의 넓이중 더 큰 것으로 갱신, 현재 넓이와 책 넓이를 더해서 갱신
                backTracking(booksIdx + 1, max(curHeight, shelfHeight + books[booksIdx][1]), curWidth + books[booksIdx][0],
                            shelfHeight)

            # 위로 쌓는 경우
            # 책 idx를 1 증가 시키고 지금 쌓는 책의 높이를 더해서 높이를 갱신,
            backTracking(booksIdx + 1, curHeight + books[booksIdx][1], books[booksIdx][0],shelfHeight + books[booksIdx - 1][1])

        backTracking(1, books[0][1], books[0][0], 0)

        return answer[0]