greentea31's Note

https://leetcode.com/problems/single-number/

풀이 과정

배열에서 딱 한번만 나오는 원소를 출력하는 문제이다.

비트 연산중에 XOR 연산은 비트가 같으면 0, 다르면 1을 출력한다. 0을 저장하고 있는 변수에 배열의 모든 원소들을 XOR 연산을 하면 2번씩 나온 원소들은 bit 연산중 0으로 바뀌고 1번 나온 원소의 bit만 남게될 것이다.

소스 코드

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for num in nums:
            answer ^= num
        return answer

https://leetcode.com/problems/search-a-2d-matrix-ii/

풀이 과정

행, 열 단위로 정렬되어 있는 2차원 배열에서 target 값이 존재하는지 여부를 판단하는 문제이다.

2차원 배열의 값들과 target의 값을 일일이 비교해보는 방법으로도 찾을수 있지만, 행 열 단위로 정렬되어 있다는 조건이 주어졌으므로 더 빠르게 문제를 해결할 수 있다.

시작 위치를 2차원 배열의 오른쪽 위 끝 혹은 왼쪽 아래 끝으로 잡은 뒤 배열 요소의 값과 target 값과의 대소 비교후 index를 바꾸면서 찾아가는 것이다. 이러면 모든 배열의 요소를 점검 할 필요가 없다.

소스 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        
        m = len(matrix)
        n = len(matrix[0])
        
        a = 0
        b = n - 1
        
        while 0 <= a < m and 0 <= b < n:
            if matrix[a][b] == target:
                return True
            elif matrix[a][b] < target:
                a += 1
            else:
                b -= 1
        
        return False

https://leetcode.com/problems/intersection-of-two-arrays/

풀이 과정

두 배열의 교집합을 구하는 문제이다.

리스트를 set 자료형으로 바꾼다음에 s1.intersection(s2) 혹은 s1 & s2로 파이썬 내장 함수를 이용하는 방법이 가장 편리한 풀이방법이다.

O(N^2) 방법으로 브루트 포스로도 풀 수는 있다.

자료형 내장 함수도, 브루트 포스도 싫다! 하면 두 리스트를 모두 정렬후 투 포인터로 문제를 해결하면 된다.

포인터 2개 설정하고 맨 앞에 포인터를 설정한 뒤 포인터가 가리키고 있는 값끼리 비교하고, 같으면 정답에 추가, 한 쪽이 작으면 작은쪽의 포인터를 한 칸 전진하는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = set()
        nums1.sort()
        nums2.sort()
        len1 = len(nums1)
        len2 = len(nums2)
        index1 = 0
        index2 = 0
        
        while index1 < len1 and index2 < len2:
            if nums1[index1] < nums2[index2]:
                index1 += 1
            elif nums1[index1] > nums2[index2]:
                index2 += 1
            else:
                answer.add(nums1[index1])
                index1 += 1
                index2 += 1
        
        return answer

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = set(nums1)
        nums2 = set(nums2)
        return nums1 & nums2

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

풀이 과정

오름차순으로 정렬된 배열이 회전되어져서 주어질 때, target값의 인덱스를 O(logN)으로 구하는 문제이다. 없으면 -1을 리턴하면 된다.

O(logN)으로 구해야 하므로 배열을 전부 살펴보며 target값이 있는지 확인하는 O(N) 방법은 사용할 수 없다. 몇번 회전되어 있는지를 구하고 다시 회전시키고 이진 탐색을 수행하면 좋을 것 같은데 몇번 회전되어 있는지를 구하는 연산도 O(N)이다... 이런....

0 1 2 3 4 5 6 이라는 배열을 생각해보자. 이 배열을 회전시키면

        mid

0 1 2 3 4 5 6

1 2 3 4 5 6 0

2 3 4 5 6 0 1

3 4 5 6 0 1 2

4 5 6 0 1 2 3

5 6 0 1 2 3 4

6 0 1 2 3 4 5

이다. 처음 값을 left로 두고 마지막 값을 right로 두고 while left <= right으로 이진 탐색을 수행한다고 할 때 다음과 같은 생각을 할 수 있다.

nums[left] < nums[mid]가 성립한다면? 일단 left ~ mid까지는 정렬이 되어있다는 소리고 (중간에 대소관계의 역전이 발생하지 않음) 그 안에서는 이진 탐색을 수행할 수 있을 것이다.

nums[left] < nums[mid]가 성립하지 않는다면? nums[mid] < nums[right]는 무조건 성립하고 그 안에서는 이진 탐색을 수행할 수 있다. 0 1 2 3 4 5 6 을 회전시킨 배열들을 보면서 대입해보면 이해가 편리하다.

nums[left] < nums[mid]가 성립했다면? nums[left] <= target <= nums[mid]인지 체크해서 왼쪽 배열에 target값이 존재하는지 판단할 수 있다. 없으면 오른쪽 배열에 있을 가능성이 있으므로 오른쪽을 찾아봐야 한다.

이와 유사한 논리로 왼쪽 정렬되어 있는데 왼쪽에 있는 경우, 없는 경우 그리고 오른쪽이 정렬되어 있는데 오른쪽에 있는 경우, 없는 경우... 이렇게 모두 따져보면 이진 탐색이 가능함을 알 수 있다.

소스 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        mid = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

https://leetcode.com/problems/binary-search/

풀이 과정

이진 탐색으로 target이 배열에 존재하면 target의 index를, 아니면 -1을 출력하는 문제이다.

배열이 정렬된 상태로 들어오므로 이진 탐색으로 탐색 범위를 반씩 줄여나가면서 target을 빠르게 찾을 수 있다.

소스 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        mid = (left + right) // 2
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1 
        
        return -1

https://leetcode.com/problems/k-closest-points-to-origin/

풀이 과정

유클리드 거리가 가장 가까운 k개의 좌표를 출력하는 문제이다.

그냥 모든 좌표의 유클리드 거리를 구한 뒤, 정렬해서 앞에서 k개를 출력하거나, 우선순위 큐에 넣어서 k개를 pop을 해주는 방법으로 문제를 해결할 수 있다.

소스 코드

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))
        
        answer = []
        
        for _ in range(k):
            dist, x, y = heapq.heappop(heap)
            answer.append([x, y])
        
        return answer

https://leetcode.com/problems/largest-number/

풀이 과정

여러 숫자를 앞뒤로 이어 붙여 가장 큰 숫자를 만드는 문제이다.

위의 예시에서 보이듯 3, 30, 34, 5, 9의 숫자 모음은 9, 5, 34, 3, 30 순으로 붙여야 가장 큰 수로 만들 수 있다. 커스텀 비교 연산자를 하나 선언해서 문제를 해결할 수 있다. 원래의 비교에 따르면 3과 30을 비교하면 30이 더 큰 숫자이고 34와 5를 비교하면 34가 더 큰 숫자이다. 하지만 이 문제를 해결하기 위해서는 str(x) + str(y) > str(y) + str(x)일때 참을 출력하는 커스텀 비교 연산자를 하나 만들어주어야 한다.

그러면 3과 30은 330 > 303이므로 3이 더 큰 것으로 처리되고 34와 5는 345 < 534이므로 5가 더 큰 것으로 처리될 것이다. 이와 같이 처리해야 문제의 조건을 만족할 수 있다.

소스 코드

class to_swap(str):
    def __lt__(x, y):
        return x+y > y+x

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(i) for i in nums]
        nums.sort(key=to_swap)
        return str(int(''.join(map(str, nums))))

https://leetcode.com/problems/merge-intervals/

풀이 과정

수직선 간의 주어진 구간에서, 겹치는 구간은 합병하는 문제이다.

위의 예시는 1~3 2~6은 겹치는 부분이니 1~6으로 합병한 예시임을 확인할 수 있다.

intervals을 리스트 내의 첫번째 원소를 기준으로 정렬해준 뒤, 각 구간의 현재 시작, 끝점과 이전 시작, 끝점을 비교하면서 이전 끝점이 현재 시작점보다 크면 합병을 해주는 방식으로 진행하였다. 합병 도중 이전 끝점이 현재 끝점보다 크면 합병 구간이 현재 끝점으로 당겨지는 경우가 없도록 예외 처리를 해주어야 한다.

소스 코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        prev_start, prev_end = intervals[0][0], intervals[0][1]
        answer = []
        
        for start, end in intervals:
            if prev_end >= end:
                continue
            if prev_end >= start:
                prev_end = end
                continue
            else:
                answer.append([prev_start, prev_end])
                prev_start, prev_end = start, end
        
        answer.append([prev_start, prev_end])
        
        return answer

https://leetcode.com/problems/sort-list/

풀이 과정

연결 리스트를 정렬하는 문제이다.

연결 리스트를 merge sort로 정렬해주거나, 연결 리스트를 리스트에 담고 내장 함수 sort() 이용후 다시 리스트에 담는 두 방법 중 한가지를 이용해주면 문제를 해결할 수 있다.

소스 코드

연결 리스트 -> 리스트 -> 연결 리스트

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p = head
        lst = []
        
        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

merge sort

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
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: Optional[ListNode]) -> Optional[ListNode]:
        # head, head.next 둘다 null이면
        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)

https://leetcode.com/problems/kth-largest-element-in-an-array/

풀이 과정

배열에서 K번째 큰 원소를 반환하는 문제이다.

내림차순 정렬 후 K번째 원소를 찾아서 반환해주거나, 리스트를 힙으로 변환해 준 후, K번째 큰 원소가 나오도록 pop을 여러번 반복해주면 된다.

소스 코드

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums, reverse=True)[k-1]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        length = len(nums)
        for _ in range(length - k):
            heapq.heappop(nums)
        return heapq.heappop(nums)