리스트에서 n번째로 큰 요소를 선형 시간 복잡도(O(n))로 선택하려면 두 가지 핵심 동작이 필요합니다. 하나는 특정 구간에서 가장 큰(또는 기준이 되는) 요소를 찾는 방법이고, 다른 하나는 사용자가 입력한 'i' 값을 기준으로 리스트를 두 부분으로 분할하는 방법입니다. 이 기법은 퀵정렬(Quick Sort)의 파티션 개념을 응용한 퀵셀렉트(Quickselect) 알고리즘과 유사하며, 전체를 정렬하지 않고도 원하는 순위의 요소를 빠르게 찾을 수 있습니다.
아래는 이를 구현한 예시입니다.
예제 코드
def select_largest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = end - pivot_val
if i < k:
return select_largest(my_list, pivot_val + 1, end, i)
elif i > k:
return select_largest(my_list, beg, pivot_val, i - k)
return my_list[pivot_val]
def start_partition(my_list, beg, end):
pivot_val = my_list[beg]
i = beg + 1
j = end - 1
while True:
while (i <= j and my_list[i] <= pivot_val):
i = i + 1
while (i <= j and my_list[j] >= pivot_val):
j = j - 1
if i <= j:
my_list[i], my_list[j] = my_list[j], my_list[i]
else:
my_list[beg], my_list[j] = my_list[j], my_list[beg]
return j
my_list = input('Enter the list of numbers.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('Enter the value for i.. '))
ith_largest = select_largest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_largest))실행 결과
Enter the list of numbers.. 34 67 12 0 999 Enter the value for i.. 1 The result is 999.
코드 설명
'select_largest'라는 함수가 정의되며, 리스트와 시작 인덱스(beg), 끝 인덱스(end), 그리고 'i' 값을 매개변수로 받습니다.
또 다른 함수인 'start_partition'은 피벗(pivot) 값을 기준으로 리스트를 두 부분으로 나누는 역할을 합니다.
이 파티션 함수는 'select_largest' 내부에서 호출됩니다.
'select_largest' 함수는 자기 자신을 다시 호출하는데, 이것이 바로 재귀(recursion)가 동작하는 방식입니다. 조건에 따라 탐색 범위를 절반 수준으로 좁혀 가며 원하는 요소에 도달합니다.
사용자로부터 숫자 목록을 입력받습니다.
입력받은 문자열은 공백을 기준으로 분할(split)됩니다.
분할된 각 값은 정수(int)로 변환되어 리스트에 저장됩니다.
사용자로부터 'i' 값(몇 번째로 큰 값인지)을 입력받습니다.
이 'i' 값을 기준으로 리스트가 두 부분으로 나뉘며, 불필요한 부분은 더 이상 탐색하지 않습니다.
해당 범위의 리스트에 대해 'select_largest' 함수가 재귀적으로 호출됩니다.
최종 결과가 콘솔에 출력됩니다.
예제 실행 결과에서 입력값 34, 67, 12, 0, 999 중 1번째로 큰 값은 999이므로 결과가 올바르게 출력된 것을 확인할 수 있습니다. 이 방식은 평균적으로 O(n)의 시간 복잡도를 가지므로, 대량의 데이터에서 특정 순위의 값을 구할 때 매우 효율적입니다.