Reverse Nodes in k-Group

Q: k개 그룹으로 노드를 뒤집는 시간 및 공간 복잡도는 얼마인가요?

L 개의 노드로 이루어진 리스트에 대해 O(L) 시간으로 실행됩니다. 각 노드는 한 번씩 세고 한 번씩 뒤집습니다. 제자리 버전은 O(1)의 추가 메모리를 사용하고, 값을 배열에 복사하면 O(L)을 사용합니다.

Q: 마지막 그룹에 k개보다 적은 노드가 있으면 어떻게 되나요?

원래 순서를 유지합니다. 각 그룹을 뒤집기 전에 k 개의 노드를 세고, 목록의 끝에 먼저 도달하면 나머지는 그대로 둡니다.

어려움연결 리스트

+10

단일 연결 리스트는 같은 길이의 두 배열에 저장됩니다. 노드 i는 values[i]를 가지며 노드 next[i]를 가리킵니다. -1은 리스트의 끝을 나타내고, 헤드는 노드 0입니다. 노드는 어떤 순서로든 저장될 수 있으므로 배열 순서가 아니라 링크를 따라가세요.

리스트를 k개 노드씩 그룹으로 나누어 뒤집으세요. 처음 k개 노드는 역순이 되고, 다음 k개도 같은 방식으로 처리합니다. 이런 식으로 계속하세요. k개보다 적은 마지막 그룹은 순서를 유지합니다. 새로운 리스트 순서대로 값을 반환하세요.

함수

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

nextinteger-array: 각 노드가 연결되는 노드의 인덱스 또는 마지막 노드의 경우 -1
valuesinteger-array: 각 노드가 보유한 값
kinteger: 각 그룹에서 뒤집을 노드의 수
반환값integer-array: 새 목록 순서의 값

제약 조건

1 ≤ L ≤ 5000이며, 여기서 L은 next와 values의 길이입니다.
-1000 ≤ values[i] ≤ 1000
1 ≤ k ≤ L
각 next[i]는 -1이거나 0부터 L-1까지의 노드 인덱스입니다.
노드 0에서 시작하여 목록은 모든 노드를 정확히 한 번씩 방문한 다음 -1에 도달합니다. 사이클은 없습니다.

예제

입력: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
출력: [2, 1, 4, 3, 5]
설명: 목록은 1, 2, 3, 4, 5(노드 0, 2, 4, 1, 3)로 읽힙니다. 1, 2와 3, 4 쌍은 순서가 뒤바뀌고, 5만 k = 2보다 짧으므로 마지막에 그대로 남습니다.

입력: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
출력: [30, 20, 10, 60, 50, 40, 70, 80]
설명: 목록은 10, 20, ..., 80으로 읽힙니다. 그룹 10, 20, 30과 40, 50, 60은 역순으로 바뀝니다. 70, 80은 k = 3보다 짧으므로 순서를 유지합니다.

입력: next = [2, -1, 1]values = [7, 9, 3]k = 3
출력: [9, 3, 7]
설명: 배열은 7, 9, 3으로 읽히지만, 리스트는 7, 3, 9로 읽힙니다. k가 길이와 같으면 리스트 전체가 하나의 그룹이 되어 뒤집힌 결과인 9, 3, 7이 나옵니다.

후속 질문

한 그룹을 뒤집고 나머지 목록에 재귀적으로 적용하는 방식으로 작성할 수 있나요? 이 방식은 추가 메모리를 얼마나 사용하나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

전체 리스트를 뒤집는 것은 링크를 한 번씩 뒤집는 과정입니다. 여기서는 k개 노드마다 뒤집기를 멈추며, 뒤집힌 각 그룹을 앞부분 및 뒤에 오는 노드들과 다시 연결해야 합니다. 값을 배열에 복사한 다음 블록을 뒤집거나, O(1)의 추가 메모리만 사용해 각 그룹의 링크를 제자리에서 다시 연결할 수 있습니다.

값을 복사하고 각 블록을 뒤집으세요

핵심 아이디어

0 노드에서 시작해 node = next[node]를 따라가며 값을 리스트 순서대로 배열에 복사합니다. 이제 그룹은 0부터 k-1까지, k부터 2k-1까지 등의 인덱스 블록입니다. 블록 전체가 들어가는 경우마다 뒤집고, 더 짧은 마지막 블록은 그대로 둡니다. 이 방법은 O(L) 시간과 O(L)의 추가 메모리를 사용하며, 링크는 전혀 건드리지 않습니다.

알고리즘

노드 0에서 시작해 -1까지 이동하며 values[node]를 배열에 추가합니다.
start = 0, k, 2k, ...인 경우 start + k ≤ L인 동안, 인덱스 start부터 start+k-1까지의 블록을 뒤집습니다.
끝에 더 짧은 블록이 있으면 그대로 둡니다.
배열을 반환합니다.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

재연결하여 각 그룹을 제자리에서 역순으로 만드세요

핵심 아이디어

전체 목록을 뒤집으려면 prev와 node를 사용해 순회하면서 next[node] = prev로 설정합니다. 그룹을 뒤집을 때는 같은 루프를 k번 실행하며, prev는 그룹 바로 다음 노드인 after에서 시작합니다. 그룹의 첫 번째 노드는 마지막 노드가 되어 after에 연결되므로 나머지 목록은 그대로 이어집니다.

뒤집기 전에 k개의 노드를 셉니다. 먼저 -1에 도달하면 나머지는 짧은 그룹이므로 그대로 둡니다. 뒤집은 다음에는 prev가 그룹의 새로운 첫 번째 노드가 됩니다. 이전 그룹의 마지막 노드를 여기에 연결하거나, 첫 번째 그룹이라면 이를 헤드로 설정합니다. 그룹의 기존 첫 번째 노드는 이제 뒤집기를 마친 부분의 마지막 노드입니다.

각 노드는 두 번 방문합니다. 한 번은 세기 위해, 한 번은 뒤집기 위해 방문합니다. 시간은 O(L)이고 메모리는 정수 몇 개입니다(R에서는 처음 변경할 때 링크 벡터를 복사하므로 O(L)입니다).

알고리즘

head = 0, prevTail = -1, groupStart = 0으로 시작합니다.
groupStart에서 after까지 k단계 이동합니다. 먼저 -1에 도달하면 5단계로 갑니다.
prev = after와 node = groupStart로 설정하고, k번 반복합니다. next[node]를 저장하고, next[node] = prev로 설정한 다음, 둘 다 다음으로 이동합니다.
prevTail이 -1이면 head = prev로 설정하고, 그렇지 않으면 next[prevTail] = prev로 설정합니다. prevTail = groupStart, groupStart = after로 설정하고 2단계로 갑니다.
head에서 값을 수집합니다.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

함정과 경계 사례

마지막의 짧은 그룹을 뒤집는 것. 뒤집기 전에 노드 k개를 세세요. 뒤집힌 링크는 한 번 더 순회하지 않고는 되돌릴 수 없습니다.
전체 역순과 마찬가지로 prev = -1로 뒤집기를 시작하는 것. 그러면 짧은 꼬리 부분이 떨어져 나갑니다. 첫 번째 예제는 2, 1, 4, 3을 반환합니다.
이전 그룹의 마지막 노드를 새 첫 번째 노드에 연결하지 않는 것. 이전 그룹의 마지막 노드는 여전히 기존 첫 번째 노드를 가리키므로 k-1개의 노드가 사라집니다.
노드 0에서 답을 읽거나 values를 왼쪽에서 오른쪽으로 읽는 것. k ≥ 2인 그룹을 뒤집으면 노드 0은 머리 노드가 아니며, 배열의 순서는 애초에 리스트의 순서가 아니었습니다.
배열이 1부터 시작하는 Lua와 R에서 0부터 인덱싱하는 것. 노드 인덱스는 0부터 유지하고 next[node + 1]을 읽으세요.

자주 묻는 질문3

k개 그룹으로 노드를 뒤집는 시간 및 공간 복잡도는 얼마인가요?

L개의 노드로 이루어진 리스트에 대해 O(L) 시간으로 실행됩니다. 각 노드는 한 번씩 세고 한 번씩 뒤집습니다. 제자리 버전은 O(1)의 추가 메모리를 사용하고, 값을 배열에 복사하면 O(L)을 사용합니다.

마지막 그룹에 k개보다 적은 노드가 있으면 어떻게 되나요?

원래 순서를 유지합니다. 각 그룹을 뒤집기 전에 k개의 노드를 세고, 목록의 끝에 먼저 도달하면 나머지는 그대로 둡니다.

이 문제의 해결 방법에서는 왜 더미 노드를 사용하나요?

노드 객체를 사용하면 head 앞에 더미 노드를 두어 첫 번째 그룹 앞에도 노드가 있게 하므로, 한 줄로 모든 그룹을 완료된 부분에 연결할 수 있습니다. 링크 배열을 사용할 때는 첫 번째 그룹이 끝날 때까지 prevTail이 -1로 유지되도록 하면 같은 역할을 합니다.

def reverseKGroup(next, values, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

예상 출력

[2, 1, 4, 3, 5]