배열의 각 원소에 대해 '다음 큰 요소(Next Greater Element)'를 찾는 문제는 코딩 테스트와 알고리즘 학습에서 자주 등장하는 대표 주제입니다. 이 글에서는 사용자 정의 함수를 활용해 이 문제를 파이썬으로 해결하는 과정을 예제 코드와 함께 단계별로 살펴보겠습니다.
문제 정의
주어진 배열 안의 모든 원소에 대해 다음 큰 요소를 출력해야 합니다. 여기서 다음 큰 요소란, 배열에서 해당 원소보다 오른쪽에 있는 값들 중 가장 큰 원소를 의미합니다. 오른쪽에 더 큰 원소가 하나도 존재하지 않는 경우에는 -1을 출력합니다.
입력 테스트 케이스
[12, 1, 2, 3]
출력 결과
12 -> -1 1 -> 3 2 -> 3 3 -> -1
예를 들어 첫 번째 원소 12는 오른쪽에 더 큰 값이 없으므로 -1이 출력되고, 두 번째 원소 1의 오른쪽에는 2와 3이 있으므로 그중 가장 큰 3이 다음 큰 요소가 됩니다.
예제 코드
# 다음 큰 요소를 찾는 함수 정의
def elevalue(arr):
# 배열 전체를 순회
for i in range(0, len(arr)):
# 현재 위치부터 끝까지 슬라이싱한 뒤 최댓값 계산
final = max(arr[i:])
# 현재 원소가 최댓값이면 오른쪽에 더 큰 원소가 없음
if (arr[i] == final):
print("%d -> %d" % (arr[i], -1))
else:
print("%d -> %d" % (arr[i], final))
# 드라이버 프로그램
def main():
arr = [12, 1, 2, 3]
elevalue(arr)
arr = [1, 34, 2, 1]
elevalue(arr)
if __name__ == '__main__':
main()코드 동작 원리
이 구현의 핵심 아이디어는 매우 직관적입니다. 각 인덱스 i마다 arr[i:] 슬라이싱을 통해 현재 위치부터 배열 끝까지의 부분 배열을 만들고, 그중 최댓값을 구합니다. 현재 원소가 그 최댓값과 같다면 오른쪽에 더 큰 원소가 없다는 뜻이므로 -1을 출력하고, 그렇지 않다면 해당 최댓값을 다음 큰 요소로 출력합니다.
두 번째 테스트 배열 [1, 34, 2, 1]의 실행 결과는 다음과 같습니다.
1 -> 34 34 -> -1 2 -> -1 1 -> -1
시간 복잡도 분석
각 원소마다 슬라이싱된 부분 배열에 대해 max() 연산을 수행하므로, 이 구현의 시간 복잡도는 O(n²)입니다. 또한 슬라이싱으로 새로운 리스트가 생성되기 때문에 공간 복잡도 역시 O(n)이 추가로 필요합니다. 입력 크기가 클 경우에는 스택(monotonic stack)을 활용하면 O(n) 시간에 해결할 수 있으니 성능 개선이 필요하다면 해당 방식도 함께 공부해 보길 권합니다.
마치며
이 글에서는 사용자 정의 함수와 슬라이싱, max() 함수를 조합해 배열의 각 원소에 대한 다음 큰 요소를 구하는 파이썬 구현 방법을 알아보았습니다. 코드가 짧고 직관적이라 초보자도 이해하기 쉬우며, 파이썬의 슬라이싱과 내장 함수를 실전에서 활용하는 연습에 딱 좋은 예제입니다.