알고리즘 : 정렬(Sort), 탐색(Search)

개념

 

 

정렬(Sort)

 

두개 이상의 원소로 이루어진 배열을 정해진 기준에 따라서 다시 나열하는 일이다. 파이썬에서 정렬을 할 때 대표적으로 두가지 방법이 있다.

 

• sorted() : 원래있는 리스트를 가지고 정렬된 새로운 리스트를 만드는 함수이다.

• .sort() : 해당 리스트를 정렬시키는 method이다.

L = [4,2,6,63,5,1]
L2 = sorted(L) #기존 리스트를 가지고 새로운 정렬된 리스트를 만든다.

L.sort() #기존 리스트를 정렬시킨다. 새로운 리스트 X

L2 = sorted(L, reverse=True) 
L.sort(reverse=True)

정렬의 순서를 반대로 할 때 위에 코드처럼 reverse = True 값을 주면 된다.

 

문자열 리스트 경우 알파벳 순서로 정렬한다. 대문자가 소문자보다 앞으로 온다.

 

--> 정렬에 이용하는 키를 지정 

ex) L = ['abcd', 'xyz', 'spam'] , sorted(L, key=lambda x: len(x)) => ['xyz', 'abcd', 'spam']  (글자 숫자에 따라 정렬)

ex) L = [{'name':'John', 'score':83},{'name':'Paul','score':'92'}] => L.sort(key=lambda x:x['name']) 이름 알파벳 순서대로 정렬할 수 있다.

 

 

선형탐색(Linear Search)

앞에서부터 순서대로 찾는다. => 리스트에 길이에 걸리는 시간은 {On} 이다.

 

이진탐색(Binary Search)

리스트가 이미 정렬되있었을 때 사용할 수 있다. 찾는 요소의 범위를 반씩 줄여가며 찾는다. 탐색하는데 걸리는 시간은 {Ologn} 이다.

 

 

 

 

 

문제

 

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

 

 

 

문제풀이

def solution(L, x):
    lower = 0
    upper = len(L)-1
    idk = -1
    while lower <= upper and L[lower] <= x <= L[upper]:
        middle = (lower+upper)//2
        if L[middle] == x:
            idk = middle
            break
        elif L[middle] < x:
            lower = middle
        elif L[middle] > x:
            upper = middle
    
    answer = idk
    return answer

리스트가 이미 정렬이 되었기 때문에 더 빠른 이진탐색을 사용했다.

 

idk 값을 미리 -1로 지정해두면 x가 list에 없는경우를 따로 만들 필요가 없다.

 

x 가 list안에 있는지 while 조건에서 먼저 파악하면 실행 시간을 단축시킬 수 있다. 

 

 

---

참고 : 프로그래머스(어서와! 자료구조와 알고리즘은 처음이지?)