리스트(배열)가 주어졌을 때, 그 안에서 최댓값, 최솟값, 두 번째로 큰 값, 두 번째로 작은 값을 모두 찾아야 하는 경우가 자주 있습니다. 파이썬에서는 정렬을 활용할 수도 있지만, 리스트를 단 한 번만 순회하면서 네 가지 값을 동시에 구하는 방식이 훨씬 효율적입니다.
알고리즘
1단계: 리스트 요소를 입력받습니다. 2단계: 각 숫자를 리스트의 다른 숫자들과 비교합니다. 3단계: 최댓값, 최솟값, 두 번째로 큰 값, 두 번째로 작은 값을 구합니다.
동작 원리
네 개의 변수(maxi, secondmax, mini, secondmini)를 준비한 뒤, 리스트를 한 번 순회하면서 다음 규칙에 따라 값을 갱신합니다.
- 최댓값 갱신: 현재 항목이 최댓값보다 크면, 기존 최댓값은 두 번째로 큰 값이 되고 새 항목이 최댓값이 됩니다.
- 두 번째 최댓값 갱신: 현재 항목이 최댓값보다는 작지만 두 번째 최댓값보다 크면, 해당 값으로 교체합니다.
- 최솟값 갱신: 현재 항목이 최솟값보다 작으면, 기존 최솟값은 두 번째로 작은 값이 되고 새 항목이 최솟값이 됩니다.
- 두 번째 최솟값 갱신: 현재 항목이 최솟값보다는 크지만 두 번째 최솟값보다 작으면, 해당 값으로 교체합니다.
예제 코드
# 리스트에서 최댓값, 최솟값, 두 번째로 큰 값, 두 번째로 작은 값 찾기
def maxmin(A):
maxi = secondmax = float('-inf')
mini = secondmini = float('inf')
for item in A:
# 최댓값과 두 번째로 큰 값 갱신
if item > maxi:
secondmax = maxi
maxi = item
elif maxi > item > secondmax:
secondmax = item
# 최솟값과 두 번째로 작은 값 갱신
if item < mini:
secondmini = mini
mini = item
elif mini < item < secondmini:
secondmini = item
print("Largest element is ::>", maxi)
print("Second Largest element is ::>", secondmax)
print("Smallest element is ::>", mini)
print("Second Smallest element is ::>", secondmini)
# 드라이버 코드
A = list()
n = int(input("리스트의 크기를 입력하세요 ::"))
print("숫자를 입력하세요 ::")
for i in range(n):
k = int(input())
A.append(k)
maxmin(A)
실행 결과
리스트의 크기를 입력하세요 ::6 숫자를 입력하세요 :: 12 30 2 34 90 67 Largest element is ::> 90 Second Largest element is ::> 67 Smallest element is ::> 2 Second Smallest element is ::> 12
참고 사항
위 방식은 리스트를 단 한 번만 순회하므로 시간 복잡도가 O(n)으로 매우 효율적입니다. 반면 sorted(set(A))처럼 정렬을 이용해 첫 번째·두 번째·뒤에서 두 번째·마지막 요소를 꺼내는 방법도 가능하지만, 정렬에는 O(n log n)의 시간이 걸린다는 점을 유의해야 합니다. 또한 초기값을 float('-inf')와 float('inf')로 설정하면 음수나 양수가 섞여 있는 리스트에서도 올바르게 동작한다는 장점이 있습니다.