Rotate Array
정수 배열 nums와 숫자 k가 주어집니다. 배열을 오른쪽으로 k단계 회전하세요. 한 단계마다 각 값은 오른쪽으로 한 칸 이동하고, 마지막 값은 맨 앞으로 돌아옵니다. 회전된 배열을 반환하세요.
k는 배열의 길이보다 훨씬 클 수 있습니다.
함수
- numsinteger-array
- 회전할 정수 배열
- kinteger
- 오른쪽으로 회전하려면 몇 단계인가요
- 반환값integer-array
- nums를 오른쪽으로 k단계 회전
제약 조건
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 1040 ≤ k ≤ 109
예제
- 입력
- nums = [4, 9, 1, 6, 3]k = 2
- 출력
- [6, 3, 4, 9, 1]
- 설명
- 오른쪽으로 두 단계 이동하면 마지막 두 값인 6과 3이 앞으로 옵니다. 나머지 세 값은 오른쪽으로 두 칸 이동하며 순서를 유지합니다:
[6, 3, 4, 9, 1].
- 입력
- nums = [10, 20, 30]k = 7
- 출력
- [30, 10, 20]
- 설명
- 3걸음마다 길이가 3인 배열은 시작했던 위치로 돌아오므로, 7걸음은 7 mod 3 = 1걸음과 같은 효과를 냅니다. 한 걸음이면 30이 맨 앞으로 이동합니다.
- 입력
- nums = [-5, 8]k = 4
- 출력
- [-5, 8]
- 설명
- 4 mod 2 = 0이므로, 4단계 후에는 모든 값이 제자리로 돌아오고 배열도 변경되지 않은 상태로 돌아옵니다.
후속 질문
각 값을 곧바로 (i + k) mod n로 옮기고, 그 자리에 있던 값을 계속 옮겨 가며 제자리에서 회전할 수 있을까요? 이렇게 하면 사이클이 몇 개 만들어질까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
길이가
n인 배열은n단계 후에 시작 순서로 돌아옵니다.k가 10^9일 때 실제로 의미 있는 단계는 몇 개일까요?회전 후에는 마지막
k mod n개의 값이 배열의 앞부분을 이루고, 나머지 값이 기존 순서대로 그 뒤를 따릅니다. 인덱스i의 값은 어디로 이동할까요?배열 전체를 뒤집으면 마지막 블록이 앞으로 오지만, 두 블록 모두 순서가 거꾸로 됩니다. 각 블록을 한 번 더 뒤집어 순서를 복원하세요. 각 뒤집기는 두 인덱스가 서로를 향해 이동하는 과정입니다.
풀이
n번 이동할 때마다 배열은 처음 상태로 돌아오므로, 먼저 10^9일 수도 있는 k를 k mod n으로 줄이세요. 그런 다음 두 번째 배열의 최종 인덱스에 각 값을 바로 기록하거나, 세 번 뒤집기와 O(1)의 추가 메모리를 사용해 배열 내부에서 같은 결과를 얻으세요.
각 값을 새 인덱스로 복사하세요
핵심 아이디어
k단계 후에는 인덱스 i에 있던 값이 (i + k) mod n에 위치하므로, 단계를 수행하지 않고 그 위치에 바로 쓰면 됩니다. 먼저 k를 k mod n으로 줄이세요. n만큼 회전하면 모든 값이 원래 위치로 돌아오므로, k = 7이고 n = 3이면 한 단계만 남습니다.
한 번의 순회로 n개의 값을 모두 배치합니다. 시간은 O(n)이고, 결과를 저장하는 데 O(n)의 메모리가 추가로 필요합니다. 이런 방식으로 nums에 직접 쓸 수는 없습니다. 각 쓰기 작업이 아직 옮기지 않은 값을 덮어쓰기 때문입니다.
알고리즘
n을nums의 길이로 설정하고k를k mod n으로 바꿉니다.- 길이가
n인 결과 배열을 만듭니다. - 각 인덱스
i에 대해nums[i]를result[(i + k) mod n]에 저장합니다. - 결과를 반환합니다.
def rotate(nums, k):
n = len(nums)
k %= n # a full turn of n steps changes nothing
result = [0] * n
for i in range(n):
result[(i + k) % n] = nums[i]
return result제자리에서 세 번 뒤집기
핵심 아이디어
배열을 첫 번째 n-k개 값인 A와 마지막 k개 값인 B로 나눕니다. 회전된 배열은 B 뒤에 A를 붙인 것으로, 각 블록의 순서는 원래 순서와 같습니다. 배열 전체를 뒤집으면 블록의 순서와 각 블록 내부의 순서가 모두 뒤집히므로, B가 먼저 오지만 역순으로 읽히고 A도 마찬가지입니다. 각 블록을 다시 뒤집으면 블록 내부의 순서가 복원됩니다.
[4, 9, 1, 6, 3]과 k = 2의 경우: 전체를 뒤집으면 [3, 6, 1, 9, 4]가 되고, 처음 두 개를 뒤집으면 [6, 3, 1, 9, 4]가 되며, 마지막 세 개를 뒤집으면 [6, 3, 4, 9, 1]이 됩니다.
각 값은 최대 두 번 교환되므로 시간 복잡도는 O(n)이고, 추가 메모리는 몇 개의 인덱스 변수뿐입니다(R에서는 뒤집기 도우미 함수가 벡터를 변경할 때 벡터를 복사하므로 O(n)입니다).
알고리즘
n을nums의 길이로 설정하고k를k mod n으로 바꿉니다.- 전체 배열의 인덱스 0부터
n-1까지를 뒤집습니다. - 첫 번째 블록의 인덱스 0부터
k-1까지를 뒤집습니다. - 두 번째 블록의 인덱스
k부터n-1까지를 뒤집습니다. nums를 반환합니다.
def rotate(nums, k):
n = len(nums)
k %= n # a full turn of n steps changes nothing
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, n - 1) # the last k values come to the front, backwards
reverse(0, k - 1) # put the front block back in order
reverse(k, n - 1) # and the back block
return nums
함정과 경계 사례
k mod n을 잊는 경우.k = 10^9이면 한 단계씩 회전하는 작업은 끝나지 않으며, 처음k개의 값을 뒤집으면 배열의 끝을 훨씬 넘어 읽게 됩니다.- 모듈로 연산 없이 슬라이싱하는 경우. Python에서
k = 7이고n = 3일 때nums[-k:] + nums[:-k]는 두 슬라이스가 모두 배열의 경계에서 끝나므로 배열을 변경하지 않고 반환합니다. - 잘못된 순서로 뒤집는 경우. 두 블록을 먼저 뒤집고 전체 배열을 마지막에 뒤집으면 왼쪽 회전이 됩니다.
- 블록 경계에서 인덱스가 하나 어긋나는 경우: 첫 번째 블록은 인덱스
k-1에서 끝나고 두 번째 블록은k에서 시작합니다. 1부터 세는 Lua와 R에서는 블록이1..k와k+1..n입니다.
자주 묻는 질문3
Rotate Array의 시간 복잡도는 무엇인가요?
복사 방식과 세 번의 뒤집기 모두 O(n)입니다. 각 값이 상수 횟수만큼 이동하기 때문입니다. 먼저 k를 k mod n으로 줄이면 아주 큰 k도 문제가 되지 않습니다. 한 번에 한 단계씩 회전하면 대신 O(n × k)의 비용이 듭니다.
k가 배열의 길이보다 크면 어떻게 될까요?
n번 이동할 때마다 배열은 시작 순서로 돌아오므로 k mod n번 이동만 중요합니다. [10, 20, 30]을 7번 회전하는 것은 1번 회전하는 것과 같으며, 결과는 [30, 10, 20]입니다. k가 n의 배수이면 배열은 바뀌지 않습니다.
배열을 왼쪽으로 회전하려면 어떻게 해야 하나요?
k만큼 왼쪽으로 회전하는 것은 n - (k mod n)만큼 오른쪽으로 회전하는 것과 같습니다. 뒤집기를 사용하면 먼저 처음 k mod n개의 값을 뒤집고, 그다음 나머지 값을 뒤집은 뒤, 마지막으로 전체 배열을 뒤집습니다. 두 방법 모두 시간 복잡도는 O(n)입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def rotate(nums, k):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [4, 9, 1, 6, 3] k = 2
예상 출력
[6, 3, 4, 9, 1]