연결 리스트(Linked List)가 주어졌을 때, 이 리스트가 감소 순서(non-increasing order)로 정렬되어 있는지 확인하는 두 가지 함수를 만들어야 합니다. 하나는 반복문(iterative) 방식으로 동작하고, 다른 하나는 재귀(recursive) 방식으로 동작합니다.
예를 들어 입력이 L = [15, 13, 8, 6, 4, 2]라면 각 요소가 앞의 요소보다 작거나 같은 값으로 계속 줄어들므로 출력 결과는 True가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- solve_iter() 함수 정의 – 매개변수로 헤드(head) 노드를 받습니다.
- 헤드가 None이면 True를 반환합니다.
- 헤드의 next가 None이 아닌 동안 다음을 반복합니다:
- current := head
- current의 값이 current.next의 값보다 작거나 같으면 False를 반환합니다.
- head := head.next로 이동합니다.
- 루프가 끝나면 True를 반환합니다.
- solve_rec() 함수 정의 – 마찬가지로 헤드 노드를 받습니다.
- 헤드가 None이거나 헤드의 next가 None이면 True를 반환합니다.
- 현재 노드의 값이 다음 노드의 값보다 크고, 재귀 호출 결과도 참일 때만 True를 반환합니다.
예제 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
class ListNode: def __init__(self, data, next = None): self.val = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def solve_iter(head): if head == None: return True while head.next != None: current = head if current.val <= current.next.val: return False head = head.next return True def solve_rec(head): if head == None or head.next == None: return True return head.val > head.next.val and solve_rec(head.next) L = make_list([15, 13, 8, 6, 4, 2]) print(solve_iter(L)) print(solve_rec(L))
입력
[15, 13, 8, 6, 4, 2]
출력
True True
코드 설명 및 복잡도 분석
make_list() 함수는 파이썬 리스트를 받아 연결 리스트로 변환하는 유틸리티 함수입니다. 첫 번째 요소로 헤드 노드를 생성한 뒤, 나머지 요소들을 순회하며 리스트 끝에 노드를 하나씩 추가합니다.
solve_iter() 함수는 반복문 방식입니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 추가 메모리 없이 효율적으로 동작합니다. 인접한 두 노드의 값을 비교하다가 오름차순 구간을 발견하면 즉시 False를 반환합니다.
solve_rec() 함수는 재귀 방식입니다. 논리 AND 연산(<code>and</code>)을 활용해 현재 노드와 다음 노드의 크기 비교 결과와 재귀 호출 결과를 한 줄로 결합합니다. 시간 복잡도는 O(n)이지만, 호출 스택이 쌓이므로 공간 복잡도는 O(n)입니다. 따라서 리스트가 매우 긴 경우에는 반복문 방식이 더 안전합니다.