Junhyuk Yu

I will be an amazing person.

해당 내용은 ‘파이썬 알고리즘 인터뷰’ 책의 일부를 발췌하여 정리한 내용입니다.

알고리즘

알고리즘 파트에서는 알고리즘의 꽃이라 할 수 있는 정렬 알고리즘을 시작으로, 큰 수도 쉽게 찾아내는 이진 검색, 컴퓨터의 기본 개념이자 근간을 이루고 있는 비트 단위 조작 방법에 대하여 포스팅할 예정이다.

정렬

정렬 알고리즘은 목록의 요소를 특정 순서대로 넣는 알고리즘이다. 대개 숫자식 순서(Numerical Order)와 사전식 순서(Lexicographical Order)로 정렬한다.

리스트 정렬

연결 리스트를 O(nlogn)에 정렬하라.

Input: head = [4,2,1,3]
Output: [1,2,3,4]
  • 풀이: 병합 정렬
class Solution:
    # 두 정렬 리스트 병합
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            l1.next = self.mergeTwoLists(l1.next, l2)

        return l1 or l2

    def sortList(self, head: ListNode) -> ListNode:
        if not (head and head.next):
            return head

        # 런너 기법 활용
        half, slow, fast = None, head, head
        while fast and fast.next:
            half, slow, fast = slow, slow.next, fast.next.next
        half.next = None

        # 분할 재귀 호출
        l1 = self.sortList(head)
        l2 = self.sortList(slow)

        return self.mergeTwoLists(l1, l2)
  • 풀이: 내장 함수 이용
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # 연결 리스트 -> 파이썬 리스트
        p = head
        lst: List = []
        while p:
            lst.append(p.val)
            p = p.next

        # 정렬
        lst.sort()

        # 파이썬 리스트 -> 연결 리스트
        p = head
        for i in range(len(lst)):
            p.val = lst[i]
            p = p.next
        return head

구간 병합

겹치는 구간을 병합하라.

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
  • 풀이: 정렬하여 병합
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # return값을 넘겨줄 list 생성
        merged = []

        # intervals의 0번째 값을 기준으로 정렬하여 for문
        for i in sorted(intervals, key= lambda x: x[0]):
            # merged 속 마지막값의 최대값이 i의 최소값보다 클 경우
            if merged and i[0] <= merged[-1][1]:
                # max를 통해서 최대값을 바꿔줌
                merged[-1][1] = max(merged[-1][1], i[1])
            else:
                # += i, : 콤마연산자. 중첩리스트를 만들어주는 역할
                merged += i,

        return merged

삽입 정렬 리스트

연결리스트를 삽입 정렬로 정렬하라.

Input: head = [4,2,1,3]
Output: [1,2,3,4]
  • 풀이: 삽입 정렬
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = parent = ListNode(0)
        while head:
            while cur.next and cur.next.val < head.val:
                cur = cur.next

            cur.next, head.next, head = head, cur.next, head.next

            if head and cur.val > head.val:
                cur = parent

        return parent.next

가장 큰 수

항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하라.

Input: nums = [10,2]
Output: "210"
---
Input: nums = [3,30,34,5,9]
Output: "9534330"
  • 풀이: 삽입 정렬
class Solution:
		# 스왑을 해줄 함수를 정의
    @staticmethod
    def to_swap(n1: int, n2: int) -> bool:
        return str(n1) + str(n2) < str(n2) + str(n1)

    def largestNumber(self, nums: List[int]) -> str:
        i = 1

        while i < len(nums):
            j = i
            while j > 0 and self.to_swap(nums[j - 1], nums[j]):
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
                j -= 1
            i += 1

        return str(int(''.join(map(str, nums))))
  • 풀이: 가장 빠른 처리 속도
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        for i, n in enumerate(nums):
            nums[i] = str(n)
        
        def compare(nums1, nums2):
            if nums1 + nums2 > nums2 + nums1:
                return -1
            else:
                return 0        
        nums = sorted(nums,key= cmp_to_key(compare))
        str_list = ''.join(nums)
        num_str = str_list.lstrip("0")
        if(not num_str):
            num_str = "0"
        return num_str

🤔 cmp_to_key란?

functool.cmp_to_key()로서, sorted 함수의 key 매개변수에 함수를 전달할 때 사용한다. 즉, 직접 정렬하는 함수를 만들어 그것을 key에 적용시키는 방식이라 볼 수 있다.

유효한 에너그램

t가 s의 애너그램인지 판별하라.

Input: s = "anagram", t = "nagaram"
Output: true
---
Input: s = "rat", t = "car"
Output: false
  • 풀이: 정렬을 이용한 비교
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

색 정렬

빨간색을 0, 흰색을 1, 파란색을 2라할 때 순서대로 인접하는 제자리 정렬을 수행하라.

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
---
Input: nums = [2,0,1]
Output: [0,1,2]
  • 풀이: .sort() 함수 사용
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        return nums.sort()

  • 풀이: 네덜란드 국기 문제를 응용한 풀이

    이 풀이는 양쪽에 포인터를 두고 가운데 값을 기준으로 스왑하는 형태로 구현되는 코드다.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        red, white, blue = 0, 0, len(nums)

        while white < blue:
            if nums[white] < 1:
                nums[red], nums[white] = nums[white], nums[red]
                white += 1
                red += 1
            elif nums[white] > 1:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            else:
                white += 1

원점에서 k번째로 가까운 점

원점에서 k번째로 가까운 점 목록을 순서대로 출력하라.

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
---
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
  • 시도한 풀이
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points_length = {}

        for point in points:
            length = (point[0] ** 2 + point[1] ** 2) ** (1/2)
            points_length[length] = point

        points_length = sorted(points_length.items())
        answer = []

        for i, j in points_length:
            answer.append(j)        
        
        return answer[:k]

대부분의 case에서는 통과가 되었지만 points = [[1,0], [0,1]], k = 2와 같이 거리가 같은 경우, 딕셔너리 중복으로 인해서 좌표값이 제대로 입력되지 않아 오류가 발생하였다.

  • 풀이: heapq를 이용한 풀이
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []

        for (x, y) in points:
            # 결국 루트는 거리를 정확하게 표현하기 위한 수단일 뿐, 순서를 맞추는데는 필요가 없기에 계산 과정을 생략
            dist = x ** 2 + y ** 2
            heapq.heappush(heap, (dist, x, y))

        result = []

        for _ in range(k):
            # heapq의 모듈은 최소 힙으로 되어있기에 dist가 가장 가까운 순으로 pop이 된다.
            (dist, x, y) = heapq.heappop(heap)
            result.append((x, y))

        return result
  • 풀이: 가장 빠른 응답시간
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        return sorted(points, key = lambda x : x[0]*x[0] + x[1]*x[1])[:k]

You may also enjoy