sorted()
sort()
reverse = True
: 내림차순으로 정렬하고 싶을 때 사용( e.g. [10, 9, 8, 7, 6])
문자열로 이루어진 리스트의 경우
문자열 길이로 정렬하려면
// example_1
>>> L = ['abcd', 'xyz', 'spam']
>>> sorted(L, key=lambda x: len(x))
['xyz', 'abcd', 'spam']
>>> L = ['spam', 'xyz', 'abcd']
>>> sorted(L, key=lambda x: len(x))
['xyz', 'spam', 'abcd']
// example_2
>>> L=[{'name':'john', 'score':83}
,{'name':'Paul', 'score':92}]
>>> L.sort(key=lambda x: x['score'], reverse=True)
>>> L
[{'name': 'Paul', 'score': 92}, {'name': 'john', 'score': 83}]
// linear.py
def linear_search(L, x):
i = 0
while i < len(L) and L[i] != x:
i += 1
if i < len(L):
return i
else:
return -1
>>> S = [3, 8, 2, 7, 6, 10, 9]
>>> linear_search(S, 6)
4
>>> linear_search(S, 1)
-1
>>> linear_search(S, 11)
Traceback (most recent call last):
ValueError: 11 is not in list
lower = 0
upper = len(L) - 1
idx = -1
while lower <= upper:
middle = (lower + uppser) // 2
if L[middle] == target:
...
elif L[middle] < target:
lower = ...
else:
upper = ...
어서와! 자료구조와 알고리즘은 처음이지? - 3강 실습: 이진탐색
리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.
예를 들어,L = [2, 3, 5, 6, 9, 11, 15]x = 6의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.
또 다른 예로,L = [2, 5, 7, 9, 11]x = 4로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.
이 연습문제에서는 알고리즘의 효율성도 평가합니다. 만약 순차 (선형) 탐색 알고리즘을 구현하는 경우에는 제한 시간 요구사항을 만족하지 못하여 효율성 테스트 케이스들을 통과하지 못할 수도 있습니다.
def solution(L, x):
answer = -1
lower = 0
upper = len(L) - 1
if x in L:
while lower <= upper:
middle = (lower + upper) // 2
if L[middle] == x:
answer = middle
break
elif L[middle] < x:
lower = middle + 1
else:
upper = middle - 1
return answer
정확성 테스트
테스트 1 〉 통과 (0.04ms, 10.8MB)
테스트 2 〉 통과 (0.04ms, 10.8MB)
테스트 3 〉 통과 (0.04ms, 10.6MB)
테스트 4 〉 통과 (0.03ms, 10.5MB)
효율성 테스트
테스트 1 〉 통과 (2.27ms, 83.3MB)
테스트 2 〉 통과 (2.77ms, 83.7MB)
테스트 3 〉 통과 (14.00ms, 387MB)
테스트 4 〉 통과 (14.36ms, 386MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0