연결 리스트(Linked List)가 하나 있다고 가정해 보겠습니다. 이 문제에서는 리스트의 앞쪽 절반을 뒤쪽 절반 위로 접어 올린 다음, 서로 겹치게 되는 노드들의 값은 합산하여 병합하고, 최종적으로 결과 연결 리스트의 헤드(head)를 반환해야 합니다.
예를 들어 입력이 [5,8,1,2,4,7,5]라면 출력은 [2, 5, 15, 10]이 됩니다.
문제 해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 노드 개수를 셀 변수
temp를 0으로 초기화합니다. - 포인터
ptr을 시작 노드로 설정한 뒤, 리스트 끝까지 이동하며 전체 길이를 셉니다. - 접을 횟수
t를temp // 2(길이의 절반)로 지정합니다. - 스택
stk를 새로 만들고, 포인터m을 시작 노드로 설정합니다. t가 0이 될 때까지 앞쪽 절반의 각 노드 값을 스택에 push하면서, 해당 노드들의 연결을 끊습니다(next = None). 이렇게 하면 앞쪽 절반이 분리됩니다.node를 뒤쪽 절반의 시작 노드로 갱신합니다.- 전체 길이가 홀수라면 중간 노드는 짝이 없으므로 그대로 두고,
m을 한 칸 앞으로 이동시켜 건너뜁니다. m이 null이 아닌 동안 다음을 반복합니다.m.val에 스택 최상단(top) 값을 더합니다.- 스택에서 pop합니다.
m을 다음 노드로 이동합니다.
- 갱신된
node를 반환합니다.
스택의 LIFO(Last-In, First-Out) 특성 덕분에 앞쪽 절반을 역순으로 꺼내 뒤쪽 절반과 정확히 맞춰 더할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n/2)입니다.
예제 코드
아래 구현 예제를 통해 더 잘 이해할 수 있습니다.
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 print_list(head):
ptr = head
print('[', end='')
while ptr:
print(ptr.val, end=', ')
ptr = ptr.next
print(']')
class Solution:
def solve(self, node):
temp = 0
ptr = node
while ptr:
temp += 1
ptr = ptr.next
t = temp // 2
m = node
stk = []
while t:
stk.append(m.val)
tmp = m.next
m.next = None
m = tmp
t -= 1
node = m
if temp % 2 != 0:
m = m.next
while m:
m.val += stk.pop()
m = m.next
return node
ob = Solution()
head = make_list([5,8,1,2,4,7,5])
print_list(ob.solve(head))입력
[5,8,1,2,4,7,5]
출력
[2, 5, 15, 10]
동작 과정 설명
입력 [5,8,1,2,4,7,5]의 경우 전체 길이는 7(홀수)입니다. 앞쪽 절반인 [5,8,1]의 값들이 순서대로 스택에 저장되고, 뒤쪽 절반은 [2,4,7,5]가 됩니다. 이후 스택에서 값이 역순으로 꺼내지면서 다음과 같이 계산됩니다.
- 2 + 1 = 2
- 4 + 8 = 5
- 7 + 5 = 15
- 중간에 짝이 없는 노드 5는 그대로 유지되어 10 위치 계산 후 결과에 포함
최종 결과는 [2, 5, 15, 10]이 됩니다.