항해99 알고리즘 13회차

문제 접근 🤔

---

• 책에서 이진 탐색에 대해 알려줘서 이진 탐색을 그대로 적용 했다.

놓쳤던 부분 😅

---

• 파이썬 라이브러리 bisect를 사용하면 더욱 단축 시킬 수 있다.

코드 😁

---

첫번 째 코드

# 197P
import sys

def component_search(array, target_array, low, high):
    result = []

    for target in target_array:
        find_check = False
        low = 0
        high = len(array) - 1
        while low <= high:
            mid = (low + high) // 2  # 중간 값 초기화
            if array[mid] == target:
                find_check = True
                break

            elif array[mid] > target:
                high = mid - 1

            elif array[mid] < target:
                low = mid + 1

        if find_check:
            result.append("yes")
        else:
            result.append("no")

    print(' '.join(result))

have_count = sys.stdin.readline().strip()  # 가지고 있는 부품 개수
have_array = list(set(map(int, sys.stdin.readline().strip().split())))  # 부품
have_array.sort()

find_count = sys.stdin.readline().strip()  # 찾는 부품 개수
find_array = list(map(int, sys.stdin.readline().strip().split()))  # 찾는 부품
find_array.sort()

component_search(have_array, find_array, 0, len(have_array) - 1)

두번 째 코드 - lib 사용

import bisect
import sys

have_count = sys.stdin.readline().strip()  # 가지고 있는 부품 개수
have_array = list(set(map(int, sys.stdin.readline().strip().split())))  # 부품
have_array.sort()

find_count = sys.stdin.readline().strip()  # 찾는 부품 개수
find_array = list(map(int, sys.stdin.readline().strip().split()))  # 찾는 부품
find_array.sort()

result_print = []
for i in find_array:
    result = bisect.bisect_left(have_array, i)
    if i == have_array[result] and result < len(have_array):
        result_print.append("yes")
    else:
        result_print.append("no")

print(' '.join(result_print))

 

Two Sum II - Input Array Is Sorted - LeetCode

Two Sum II - Input Array Is Sorted - LeetCode

문제 접근 🤔

---

• 이진 탐색으로 문제를 풀어야한다.
• combinations으로 조합을 만들고 target보다 낮은거면 넘기게 했다.
• 조합의 값이 일치하면 파이썬 이진 탐색 라이브러리로 인덱스를 담는다.

놓쳤던 부분 😅

---

• [-1, 0], -1 테스트 케이스를 통과를 못했다.
• if문 조건 때문에 안된건데, 이걸 지우고 하면 다른 테스트 케이스에서 막혔다.
• 리트코드 솔루션
  • 투 포인터를 사용
    • 맨 앞, 맨 뒤에 포인터를 지정
  • 포인터의 위치끼리 더 해준다.
    • 타겟보다 값이 클 경우에는
      • 맨 뒤를 한 칸 뒤로
    • 타겟보다 값이 작을 경우에는
      • 맨 앞을 한 칸 앞으로
  • 예) [2,7,11,15]
    • 첫번째 2, 15 = 17
      • 타겟보다 커서 맨 뒤를 한 칸 앞으로
    • 두번째 2, 11 = 13
      • 타겟보다 커서 맨 뒤를 한 칸 앞으로
    • 세번째 2, 7 = 9
      • 일치하기에 반환

코드 😁

---

첫 번째 코드 - 실패

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        temp = itertools.combinations(numbers, 2)
        for i, e in enumerate(temp):
            if e[0] > target or e[1] > target:
                continue

            # index값을 어케 구하노 ?
            if e[0] + e[1] == target:
                target_index = [(bisect.bisect_left(numbers, e[0]))+1, (bisect.bisect_left(numbers, e[1]))+1]
                return target_index

두 번째 코드 - 리트코드 솔루션

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        index = 0
        max_index = len(numbers)-1

        while index <= max_index:
            r = numbers[index] + numbers[max_index]
            if r == target:
                return [index+1, max_index+1]
            
            if r > target:
                max_index -= 1
            else:
                index += 1

        return []

 

Search a 2D Matrix II - LeetCode

Search a 2D Matrix II - LeetCode

문제 접근 🤔

---

• 그냥 무식하게 브루트 포스 방식으로 진행했다

놓쳤던 부분 😅

---

• 시간초과 뜰 줄 알았는데 안뜨는걸 보니 입력 값 확인 하고 생각해야겠다.
• 두번째 코드
  • target보다 값이 크면 다음 행으로 넘어가게 했다.
  • 시간을 2배는 줄인거같다.

코드 😁

---

첫 번째 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for x in range(len(matrix)):
            print(x)
            for y in range(len(matrix[x])):
                print(x, y)
                if target == matrix[x][y]:
                    return True

        return False

두 번째 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for x in range(len(matrix)):
            for y in range(len(matrix[x])):
                if target < matrix[x][y]:
                    continue

                if target == matrix[x][y]:
                    return True
        return False