[프로그래머스 알고리즘] 3강: 배열 - 정렬과 탐색 (Sorting & Searching)

3강 : 배열 - 정렬과 탐색

1. 정렬 (Sorting)

sorted() : 파이썬 내장함수, 정렬된 새로운 리스트 반환
sort() : 리스트 메서드, 해당 리스트 정렬

만약, 리스트가 string으로 이뤄져 있다면 알파벳 순서 따라서 정렬된다.

정렬 기준을 사용자가 직접 정하고 싶을때는 key 파라미터를 이용하여 정렬을 해준다.

EX1) x의 길이를 기준으로 리스트를 정렬하여라.

sorted(L, key = lambda x: len(x))

EX2) L이 name과 score로 이뤄진 딕셔너리가 든 리스트라 할 때, score를 기준으로 정렬하여라.

L.sort(key = lambda x: x['score'], reverse = True)

2. 탐색 (Searching)

• 선형탐색 (Linear Search)
  • 리스트를 처음부터 순차적으로 찾아나가는 방식
  • O(n), 리스트 길이에 비례하는 시간 소모
• 이진탐색 (Binary Search)
  • 리스트의 중간 지점에 있는 원소와 찾으려는 값을 비교해나가는 방식
  • 리스트가 이미 정렬되어 있는 경우에만 적용 가능
  • O(log n)의 시간 소모

3강 과제 : 이진탐색 함수

def solution(L, x):
    answer = 0
    lower = 0
    upper = len(L) - 1
    while lower <= upper:
        mid = (lower + upper)//2
        if L[mid] < x:
            lower = mid + 1

        elif L[mid] > x:
            upper = mid - 1

        elif L[mid] == x:
            answer = mid
            break

    if lower > upper:
        answer = -1

    return answer