[python] 코드 공부 : array와 sort 다루기

알고리즘 문제를 푸는 것에 있어서 중요한 것

문제는 여러가지 풀이 방법이 있을 수 있다는 것을 염두해두자
항상 예외가 있음을 잊지 말자
내가 풀어낸 답이 베스트인지 의심하자
앞서 알고리즘 문제 풀이를 수학 문제 푸는 것에 비유한 만큼 알고리즘 기반 지식도 중요하다. 제일 빠르고 쉬운 방법은 책을 읽는 것이고 책은 도저히 못읽겠다면 웹 문서를 통해 기반 지식을 익히자.
다 풀었다면 꼭 어딘가에 어떻게 풀었는지 정리를 하도록하자.
다른 사람의 코드를 많이 보자. 생각하지 못했던 방법을 발견할 수도 있다. 그리고 다른 사람의 코드를 참고하여 내 코드를 개선해보자.
쉽게 포기하지 말자. 최대 3시간까지는 고민해보자. 하지만 도저히 못풀겠다면 다른 사람에게 물어보는 것도 좋은 방법이다.

---

좋은 코드를 만드는 방법

1. 간결하고 가독성 좋은 코드를 만들기 위해서는?
   • 함수형 프로그래밍
   • 함수형 프로그래밍을 잘 모르더라도 일부 이용할 수 있다.
   • Python의 고차함수를 사용해보자
   • lambda, map, filter, reduce
   • 성능에 문제가 생길 수 있다면 무리해서 사용하진 말자 - 변수, 함수의 이름을 잘 정했는가? - 중복 코드를 제거했는가?
2. 가지치기를 했는가?
   • 흔히 가지치기는 백트래킹과 같은 알고리즘 기법에서 쓰는 말이지만 그 외 알고리즘에서도 중요한 기술이다.
   • 일반적으로 같은 빅오로 표현될 수 있는 로직이면 크게 성능이 개선되지는 않지만 개발자로써 좋은 코드를 짜는 것도 중요하고 프로그래머스의 채점 방식은 꽤 엄격하니 낭비되고 있는 로직이 있는지 확인해보자.
3. 각 언어의 장점/특징에 맞는 코드를 작성했는가?
   • Python의 장점을 살려서 코드를 작성해보자
4. 일관성이 있는가?
   • 코드 스타일이나 변수명을 짓는 스타일에 일관성이 있는지 확인하자

---

Linear Arrays

선형 배열은 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말한다.

Python 리스트에 활용할 수 있는 연산들

1. 리스트 길이와 관계 없는 연산들 - O(1)
   • .append()
   • .pop() -> 리스트의 원소를 리턴시키고, 본래 리스트의 원소는 없어진다.
2. 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 - O(n)
   • .insert((index),(item))
   • .del((index)) or del(list[index]) -> 따로 리턴 시키는 값은 없다.
   • .pop((index)) 위 연산들은 리스트의 길이가 길수록 실행시간이 오래걸린다.
     다른 원소들을 한칸씩 옆으로 이동시키는 작업이 추가되기 때문이다.
   • .index((item))

정렬된 리스트에서 특정 숫자가 들어갈 index 찾아내기

def binarySearch (arr, start, end, target):
    # check condition
    if end >= start:
        mid = start + (end - start)//2
       # If element is present at the middle
        if arr[mid] == target:
            return mid
           # If element is smaller than mid
        elif arr[mid] > target:
            return binarySearch(arr, start, mid-1, target)
           # Else the element greator than mid
        else:
            return binarySearch(arr, mid+1, end, target)
    else:
       # Element is not found in the array
        return start

def solution(L, x):
    L.insert(binarySearch(L,0,len(L)-1,x),x)
    return L

try except 이용해서 리스트에서 원소 찾기

인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수이다.

def solution(L, x):
    answer = []
    # 초기 배열에서의 인덱스를 보존하기 위한 변수 
    idx_ptr = 0
    try:
        while(True):
            idx = L.index(x)
            idx_ptr += idx 
            answer.append(idx_ptr)
            # 다음 index를 찾기 위해 슬라이싱 사용
            L = L[idx+1:]
            idx_ptr += 1
    # 찾고자하는 item이 없을 경우
    except ValueError:     
        if len(answer) == 0:
            return [-1]
        else :
            return answer
    
    return answer

---

정렬

해당 리스트를 정렬할 것인가. 새로운 정렬된 리스트를 만들것인가.

1. 원래 리스트를 유지하는 방법

L2 = sorted(L)
    # 정렬 순서를 반대로 만들기
L2 = sorted(L, reverse=True)

1. 해당 리스트를 정렬된 리스트로 만들기

L.sort()
    # 정렬 순서를 반대로 만들
L.sort(reverse=True)

대문자는 소문자보다 우선한다.

문자열 길이 순으로 하려면? 정렬에 이용하는 키를 지정하자!

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

상대적인 순서는 정렬 이후에도 변하지 않는다.

다음과 같은 응용도 가능하다.

L = [
    {'name':'Alice','age':25},
    {'name':'Bob','age':24}
]

L.sort(key = lambda x: x['name'])