Remove Nth Node From End of List
같은 길이의 두 배열에 저장된 단일 연결 리스트가 주어집니다. 노드 i는 값 values[i]를 가지며 노드 next[i]를 가리킵니다. -1은 리스트의 끝을 나타내고, 헤드는 노드 0입니다. 노드는 리스트 순서대로 저장되어 있지 않으므로 링크를 따라가세요.
리스트의 끝에서부터 세어 n번째 노드를 제거하세요. 이때 마지막 노드는 끝에서 1번째입니다. 남은 노드의 값을 리스트 순서대로 반환하세요.
함수
- valuesinteger-array
- 각 노드가 보유한 값
- nextinteger-array
- 각 노드가 연결되는 노드의 인덱스 또는 마지막 노드인 경우 -1
- ninteger
- 끝에서부터 세어 제거할 노드. 마지막 노드는 1입니다.
- 반환값integer-array
- 리스트 순서대로 나머지 값들, 유일한 노드가 제거되면 비어 있음
제약 조건
1 ≤ L ≤ 5000이며, 여기서L은values와next의 길이입니다.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- 각
next[i]는-1이거나0부터L-1까지의 노드 인덱스입니다. - 노드
0에서 시작해 목록은 모든 노드를 정확히 한 번씩 방문한 다음-1에 도달합니다. 순환은 없습니다.
예제
- 입력
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- 출력
- [5, 2, 6, 7]
- 설명
- 노드
0에서 링크를 따라가면 노드0, 2, 4, 1, 3을 방문하므로, 목록은5, 2, 6, 9, 7입니다. 끝에서 두 번째 노드는 값이9인 노드1이며, 이 노드를 제거하면 목록은5, 2, 6, 7이 됩니다. 배열 항목values[5-2] = 7은 제거할 노드가 아니라 마지막 노드입니다.
- 입력
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- 출력
- [20, 30, 40]
- 설명
- 노드가 4개이고
n = 4입니다. 끝에서 4번째 노드가 헤드입니다. 이제 리스트는 노드1에서 시작하며20, 30, 40순서입니다.
- 입력
- values = [42]next = [-1]n = 1
- 출력
- []
- 설명
- 유일한 노드는 헤드이자 마지막 노드입니다. 이 노드를 제거하면 빈 목록이 되므로 답은
[]입니다.
제출 시 숨은 테스트 +14개
후속 질문
먼저 길이를 세지 않고 한 번의 순회로 노드를 찾아 연결을 해제할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
리스트는 앞쪽으로만 순회하며, 노드는 끝에서부터의 거리로 정의됩니다. 길이
L을 알고 있다면, 앞에서 몇 번째 위치에 있을까요? 그리고 그 노드를 잘라내려면 어느 노드의 링크를 변경해야 할까요?길이를 알지 못해도 끝까지의 거리를 측정할 수 있습니다. 한 포인터를 다른 포인터보다
n개 노드 앞에서 시작하고 두 포인터를 함께 이동하세요. 선행 포인터가 마지막 노드에 도달하면 후행 포인터는 제거할 노드 바로 앞에 있습니다.fast를 앞으로n번 이동합니다. 이제-1이면 머리가 제거할 노드이므로, 리스트는next[0]에서 시작합니다. 그렇지 않으면next[fast] != -1인 동안slow와fast를 함께 이동한 다음,next[slow] = next[next[slow]]로 설정합니다. 머리부터 리스트를 따라가며 값을 수집합니다.
풀이
대상은 끝에서부터의 거리로 정의되지만, 단일 연결 리스트에서는 앞으로만 이동할 수 있고 끝에 도달해야만 끝이 어디인지 알 수 있습니다. 노드를 제거하려면 그 앞 노드에 있어야 합니다. 그 노드의 링크가 바뀌기 때문입니다. 리스트를 배열에 복사하거나, 노드 수를 세고 다시 순회할 수 있습니다. 고전적인 해법은 두 포인터를 n개의 링크만큼 떨어뜨려 놓는 것입니다. 그러면 앞쪽 포인터가 마지막 노드에 도달했을 때 뒤쪽 포인터는 대상 바로 앞에 위치합니다. 아래에서 L은 노드의 개수입니다.
값을 배열에 복사하기
핵심 아이디어
이 문제에서 포인터는 노드 인덱스입니다. 앞으로 이동하는 것은 node = next[node]이고, -1에 도달하면 끝을 지나간 것입니다. 첫 번째 예제에서 노드 0부터 이동하면 0 → 2 → 4 → 1 → 3 → -1이 됩니다.
끝에서부터 세기가 어려운 이유는 리스트에 위치가 없기 때문입니다. 그러니 위치를 부여하세요. 한 번 순회하며 각 값을 배열에 추가합니다. 첫 번째 예제의 경우 배열은 [5, 2, 6, 9, 7]입니다. L개의 값이 있는 배열에서 마지막 값은 인덱스 L-1에 있으므로, 끝에서 n번째 값은 인덱스 L-n에 있습니다. 여기서는 5-2 = 3이고, 값은 9입니다. 해당 값을 삭제하고 [5, 2, 6, 7]을 반환합니다.
이 방법은 올바르고 O(L) 시간에 실행되지만, 리스트 전체를 복사하며 링크는 전혀 건드리지 않습니다. 이 문제의 핵심은 리스트 자체를 수정하면서 추가 메모리를 O(1)만 사용하는 것이며, 다음 두 가지 접근 방식이 바로 그렇게 합니다.
알고리즘
- 빈 배열과
node = 0에서 시작합니다. node가-1이 아닌 동안values[node]를 추가하고next[node]로 이동합니다.- 인덱스
length - n의 항목을 삭제합니다. - 배열을 반환합니다.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return order노드의 개수를 센 다음 연결을 해제하세요
핵심 아이디어
목록에서 노드를 제거하려면 그 노드 앞에 있는 노드의 링크를 변경해 해당 노드를 건너뛰게 합니다: next[prev] = next[next[prev]]. 제거된 노드는 여전히 배열에 있지만, 헤드에서 시작하는 어떤 순회로도 다시는 해당 노드에 도달하지 않습니다.
그러니 prev를 찾으세요. 첫 번째 순회에서 노드 수를 셉니다. 헤드를 위치 0으로 세면, 대상은 위치 L-n에 있고 그 앞의 노드는 위치 L-n-1에 있습니다. 헤드에서 L-n-1번 이동하면 그 노드에 도달합니다. 첫 번째 예시에서는 L = 5이고 n = 2입니다. 두 번 이동하면 0 → 2 → 4가 되어 노드 4에 도달합니다. 이 노드는 노드 1, 즉 9에 연결되어 있습니다. next[4] = next[1] = 3으로 설정하면 목록은 5, 2, 6, 7이 됩니다.
대상 앞에 노드가 없는 경우가 하나 있습니다. 대상이 헤드일 때인 n = L입니다. 이 경우에는 다시 연결할 필요가 없습니다. 두 번째 예시처럼 목록은 0 대신 next[0]에서 시작합니다. 그런 다음 헤드부터 순회하며 답을 모읍니다. 목록을 두 번 순회하는 데는 약 2L번의 이동이 들고, 답 외에 필요한 메모리는 정수 몇 개뿐입니다.
알고리즘
- 노드
0에서-1까지 이동하며 노드 수를L로 셉니다. n == L이면 새 헤드는next[0]입니다.- 그렇지 않으면
prev를 노드0에서 시작하고L-n-1번 이동한 다음,next[prev] = next[next[prev]]로 설정합니다. - 헤드에서부터 이동하며
values[node]를 순서대로 수집합니다.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultn개의 링크만큼 떨어진 두 포인터
핵심 아이디어
L을 몰라도 "끝에서 n번째"를 찾을 수 있습니다. slow가 머리에서 기다리는 동안 fast를 n개의 링크만큼 앞서 이동시킵니다. 그런 다음 둘을 한 번에 한 링크씩 이동시킵니다. 간격은 계속 n으로 유지되므로, fast가 마지막 노드(next[fast] == -1, 위치 L-1)에 도달하면 slow는 위치 L-1-n, 즉 대상 바로 앞 노드에 있습니다. next[slow] = next[next[slow]] 한 번으로 대상을 목록에서 제외할 수 있습니다.
첫 번째 예를 따라가 보세요. fast는 두 번 이동하여 0 → 2 → 4가 됩니다. 이제 둘 다 이동합니다. slow는 2로 가고 fast는 1로 간 다음, slow는 4로 가고 fast는 3으로 갑니다. 노드 3이 마지막 노드이므로 멈춥니다. next[4]는 9인 노드 1을 가리키므로, next[4] = next[1] = 3으로 설정하면 해당 노드가 제거됩니다.
머리 노드인 경우는 자연스럽게 처리됩니다. n ≤ L이므로, 머리부터 먼저 이동하는 동안 fast가 -1에 도달하는 경우는 n = L일 때뿐이며, 바로 이때 머리가 대상입니다. 노드 객체를 사용한다면 머리 앞에 더미 노드를 두어 이 경우를 없앨 수 있습니다. 여기서는 fast == -1 확인이 같은 역할을 합니다. 대상을 찾고 연결을 끊는 데 한 번 순회하면 됩니다. 답을 출력하려면 한 번 더 순회해야 하며, 이는 어떤 방법을 사용하든 필요합니다.
알고리즘
-
fast = 0으로 설정하고fast = next[fast]를 사용해n번 이동합니다. fast == -1이면, 머리가 대상입니다. 새 머리는next[0]입니다.- 그렇지 않으면
slow = 0으로 설정하고next[fast] != -1인 동안 두 포인터를 모두 이동합니다. next[slow] = next[next[slow]]로 설정합니다.- 머리부터 순회하며
values[node]를 순서대로 수집합니다.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
함정과 경계 사례
대부분의 오답은 follower가 멈추는 위치와 head를 제거하는 경우에서 발생합니다.
- 배열 인덱스
L-n에 있는 항목을 제거하는 경우. 노드는 리스트 순서대로 저장되지 않으므로, 해당 인덱스는 보통 다른 노드를 가리킵니다. 첫 번째 예에서values[3] = 7은 마지막 노드이지,9가 아닙니다. next[fast] == -1일 때가 아니라fast == -1일 때 멈추는 경우. 그러면slow가 한 단계 더 이동해 대상 노드에 도달합니다. 단일 연결 리스트에서는 노드 자체를 기준으로 그 노드의 연결을 끊을 수 없습니다.- head인 경우를 놓치는 경우.
n = L이면 head에서 시작한 뒤fast는-1이 되고,next[fast]를 읽으면 대부분의 언어에서 오류가 발생합니다. Python은 불평 없이next[-1]을 읽고 잘못된 리스트를 반환하므로, 오류를 알아차리기가 더 어렵습니다. next[slow] = next[slow] + 1또는slow + 2로 연결을 끊는 경우. 리스트에서 이웃한 노드는 배열에서도 이웃한 위치에 있지 않습니다. 대상 노드 다음의 노드로 가는 유일한 방법은next[next[slow]]입니다.- head를 제거한 뒤 노드
0부터 답을 수집하는 경우. 최종 순회는 새 head에서 시작하세요. - 배열이 1부터 시작하는 Lua와 R에서 오프셋을 고려하지 않는 경우. 노드 인덱스는 0부터 시작하도록 유지하고
next[node + 1]을 읽으세요. Ruby와 R에서는next라는 단어를 예약어로 사용하므로, 해당 언어의 예시 코드에서는 매개변수 이름을next_로 지정합니다.
자주 묻는 질문4
연결 리스트에서 끝에서 n번째 노드를 한 번의 순회로 어떻게 제거하나요?
n만큼 간격을 둔 두 개의 포인터를 사용합니다. 첫 번째 포인터를 n개 노드만큼 앞서 이동한 다음, 첫 번째 포인터가 마지막 노드에 도달할 때까지 두 포인터를 함께 이동합니다. 이제 두 번째 포인터는 제거할 노드 바로 앞에 있으므로, 두 번째 포인터의 링크가 해당 노드를 건너뛰도록 지정합니다. 첫 번째 포인터가 앞서 이동하는 동안 리스트를 벗어나면 제거할 노드는 헤드입니다.
이 문제의 풀이에서는 왜 더미 노드를 사용하나요?
노드를 제거한다는 것은 그 앞에 있는 노드의 링크를 변경한다는 뜻이며, 헤드 앞에는 노드가 없습니다. 헤드 앞에 더미 노드를 두면 헤드를 포함한 모든 노드에 선행 노드가 생기므로, 모든 경우에 하나의 연결 해제 줄을 사용할 수 있습니다. 그러면 답은 더미 노드의 다음 노드에서 시작합니다. n단계를 지난 뒤 선행 포인터가 리스트의 끝을 벗어났는지 확인하면 추가 노드 없이 같은 경우를 처리할 수 있습니다.
끝에서 n번째 노드를 제거하는 시간 및 공간 복잡도는 얼마인가요?
노드가 L개인 목록에서는 대상이 어디에 있는지 알기 위해 끝까지 도달해야 하므로 O(L) 시간이 걸립니다. 먼저 개수를 세는 방법과 두 포인터 방법은 모두 추가 메모리 O(1)을 사용합니다. 값을 배열에 복사하면 O(L)이 사용됩니다.
투 포인터 풀이가 먼저 길이를 세는 것보다 더 빠른가요?
큰 차이는 없습니다. 둘 다 O(L)이고, 두 포인터를 함께 움직여도 두 번 순회하는 것과 비슷한 횟수만큼 이동합니다. 실제 이점은 미리 길이를 알 필요가 없다는 것입니다. 따라서 한 번만 읽을 수 있는 스트림으로 리스트가 들어오는 경우에도 이 방법을 사용할 수 있습니다. 면접관들이 보통 요구하는 것이 바로 이 단일 순회입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def removeNthFromEnd(values, next, n):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
기대값
[5, 2, 6, 7]