LeetCode의 Rotate Array 문제를 함께 풀어보도록 하겠습니다.
문제
배열 nums가 주어졌을 때, 배열 내의 원소들을 k 만큼 오른쪽으로 회전시켜라.
(단, 작성할 함수는 아무 것도 반환하지 않고 주어진 배열의 원소들의 위치만 변경해야 함)
예제 1
- 입력
nums = [1, 2, 3, 4, 5, 6, 7], k = 3- 결과
nums = [5, 6, 7, 1, 2, 3, 4]예제 2
- 입력
nums = [-1, -100, 3, 99], k = 2- 결과
nums = [3, 99, -1, -100]풀이 1
가장 쉽게 생각할 수 있는 방법은 문제에 나온데로 정직하게(?) 배열 내의 모든 원소를 우측으로 한칸씩 총 k번 이동시키는 것입니다.
원소를 이동할 때 주의할 부분은 바로 제일 마지막 원소가 될텐데요.
제일 마지막 원소는 배열 내에서 더 이상 뒤로 움직일 자리가 없기 때문에 맨 처음으로 이동시켜야 합니다.
이 아이디어를 첫 번째 예제에 한 번 적용해볼까요?
1 2 3 4 5 6 7 # 최초
7 1 2 3 4 5 6 # 우측으로 1칸씩 회전
6 7 1 2 3 4 5 # 우측으로 2칸씩 회전
5 6 7 1 2 3 4 # 우측으로 3칸씩 회전여기서 한 가지를 더 눈치를 챌 수 있는 것은 바로 배열의 크기만큼 모든 원소를 회전하면 배열이 원래의 모습으로 돌아온다는 것입니다.
예를 들어, 3개의 원소를 가진 배열로 생각을 해보면,
1 2 3 # 최초
3 1 2 # 우측으로 1칸씩 회전
2 3 1 # 우측으로 2칸씩 회전
1 2 3 # 우측으로 3칸씩 회전 ➡️ 원래 모습으로 돌아옴❗첫 번째 예제에서는 배열 안에는 7개의 원소가 있으므로 k가 3이든, 10이든 17이든 배열을 회전한 결과는 동일할 것입니다.
다시 말해, 곧이곧대로 꼭 k번 이 작업을 반복할 필요는 없고요.
k를 배열의 크기로 나눈 나머지(k % len(nums))만큼만 반복하면 됩니다.
설명드린 내용을 바탕으로 이 알고리즘을 구현해보겠습니다.
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
for _ in range(k % len(nums)):
prev = nums[-1]
for i in range(len(nums)):
nums[i], prev = prev, nums[i]그럼, 이 알고리즘의 복잡도를 분석해볼까요?
k를 회전수, n을 배열의 크기라고 했을 때, 이 알고리즘의 시간 복잡도는 이중 for 반복문으로 인해서 O(k * n)입니다.
변수 prev 외에는 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)입니다.
실행 속도 측면에서 조금 아쉬운 풀이인 것 같은데요. 더 좋은 풀이 방법은 없을까요❓
풀이 2
회전하기 전과 후의 배열을 한 번 나린히 비교해보겠습니다.
1 2 3 4 5 6 7 # before
5 6 7 1 2 3 4 # after혹시 뭔가 특이한 점을 발견하셨나요? 👀
이렇게 중간에 작대기를 넣어보면 어떤가요??
1 2 3 4 | 5 6 7 # before
5 6 7 | 1 2 3 4 # after네, 맞습니다! 이 작대기를 기준으로 앞 뒤를 바꾸면 두 배열은 동일한 형태를 갖게 됩니다. 😁
정리하면, 주어진 배열에서 적당한 지점을 찾아 반으로 가른 후에 앞 부분과 뒷 부분의 자리를 바꿔주면 회전된 배열을 바로 얻을 수 있는데요.
여기서 핵심은 저 작대기의 위치, 즉 분기점(pivot)를 정확히 찾는 것입니다.
곰곰히 생각을 해보면 왼쪽으로 회전할 때는 k, 오른쪽으로 회전할 때는 len(nums) - k가 된다는 것을 깨닫게 됩니다.
즉, 주어진 배열을 분기점을 기준으로 쪼갠 후 앞과 뒷 부분의 자리를 바꾼 후에 다시 붙여주면 회전된 배열을 얻게 됩니다. 여기서 주의할 부분은 문제에서 원하는 것은 원래 배열에 변경을 가하는 것이지 새로운 배열을 반환하는 것이 아니라는 것입니다. 따라서 마지막에 사본 배열의 모든 원소를 원래 배열에 복사해주는 작업이 필요하게 되겠네요.
자, 이제 이 로직을 그대로 코드로 작성해볼까요?
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
pivot = len(nums) - (k % len(nums))
rotated = nums[pivot:] + nums[:pivot]
for i in range(len(nums)):
nums[i] = rotated[i]이 알고리즘의 시간 복잡도는 O(n)인데요. 배열을 쪼갠 후 붙여서 새로운 배열을 만드는데 O(n) 시간이 걸리고, 새로운 배열의 원소들을 원래 배열로 복사해주는데 O(n)의 시간이 걸리기 때문입니다. (O(2n) = O(n))
주어진 배열과 동일한 크기의 새로운 배열을 만들기 때문에 공간 복잡도도 동일한 O(n)입니다.
두 번째 풀이에서는 첫 번째 풀이 대비 공간 복잡도를 희생하였지만 시간 복잡도를 향상시킨 것을 알 수 있습니다. 코딩 시험을 풀 때 흔히 사용되는 테크닉이니 참고바랍니다.
풀이 3
사실 주어진 배열을 3번만 거꾸로 돌리면 원하는 배열을 얻을 수가 있는데요.
먼저 배열 전체를 거꾸로 돌립니다.
그리고 처음 k개의 원소만 거꾸로 돌리고, 마지막으로 나머지 원소들을 거꾸로 돌립니다.
이 알고리즘을 첫 번째 예제에 적용을 해볼께요.
1 2 3 4 5 6 7 # 최초
7 6 5 4 3 2 1 # 전체 거꾸로
5 6 7 4 3 2 1 # 처음 3개의 원소만 거꾸로
5 6 7 1 2 3 4 # 나머지 원소들을 거꾸로배열 안의 원소들을 일정 범위 내에 거꾸로 돌리는 로직은 별도의 함수로 추출하는 것이 좋을 것 같습니다. 그렇지 않으면 똑같은 로직이 3번 반복되어 코드가 상당히 지저분해질 것입니다.
그래서 저는 reverse()라는 함수를 먼저 구현하고, 이 함수를 메인 함수 내에서 3번 호출하도록 코드를 작성하였습니다.
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def reverse(s, e):
while s < e:
nums[s], nums[e] = nums[e], nums[s]
s, e = s + 1, e - 1
k %= len(nums)
reverse(0, len(nums) - 1)
reverse(0, k - 1)
reverse(k, len(nums) - 1)이 알고리즘의 시간 복잡도는 O(n)입니다.
왜냐하면 reverse() 함수 내에 반복문이 하나만 있고, 이 것을 3번 호출해서 결국에는 O(3n) = O(n)이기 때문입니다.
주어진 배열 외에는 고정된 개수의 변수 s와 e만 사용하고 있기 때문에 공간 복잡도는 O(1)이 되겠네요.
이 알고리즘이 시간과 공간 측면에서 가장 최적화되었다고 볼 수 있을 것 같습니다.
마치면서
마지막 풀이 방법은 사실 상당한 직관이 필요하기 때문에 스스로 생각하지 못하셨다고 하더라도 실망하실 필요가 없습니다. 이러한 직관은 소수의 정말 똑똑하신 분이 아니면 절대 하루 아침에 길러지지 않아요. 하지만 많은 코딩 문제를 풀다보시면 자연스럽게 천천히 걸러지는 부분이니 걱정마시길 바랍니다. 😌