문제 개요
숫자로 이루어진 리스트가 주어졌을 때, 이 리스트를 왼쪽으로 k개의 요소만큼 회전시키는 메서드를 정의하는 것이 목표입니다.
예를 들어 입력이 [5,4,7,8,5,6,8,7,9,2]이고 k = 2라면, 앞의 두 요소(5, 4)가 맨 뒤로 이동하여 최종 출력은 [8,5,6,8,7,9,2,5,4,7]이 됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 저장할 새로운 배열 ret을 정의합니다.
- n := nums의 크기로 설정합니다.
- k := k mod n으로 조정하여 k가 배열 크기보다 큰 경우에도 올바르게 동작하도록 합니다.
- i := k부터 시작하여 i < n인 동안 반복하면서 nums[i]를 ret의 끝에 추가합니다.
- i := 0부터 시작하여 i < k인 동안 반복하면서 nums[i]를 ret의 끝에 추가합니다.
- ret을 반환합니다.
동작 원리
왼쪽 회전의 핵심은 인덱스 k부터 마지막 요소까지를 먼저 배치한 뒤, 그 뒤에 인덱스 0부터 k-1까지의 요소를 이어 붙이는 것입니다. 예를 들어 k = 2라면 세 번째 요소부터 끝까지 먼저 담고, 그다음 첫 두 요소를 덧붙이면 원하는 회전 결과를 얻을 수 있습니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> solve(vector<int>& nums, int k) {
vector <int> ret;
int n = nums.size();
k %= n;
for(int i = k; i < n; i++){
ret.push_back(nums[i]);
}
for(int i = 0; i < k; i++){
ret.push_back(nums[i]);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {5,4,7,8,5,6,8,7,9,2};
print_vector(ob.solve(v, 3));
}입력
{5,4,7,8,5,6,8,7,9,2}, 2출력
[8, 5, 6, 8, 7, 9, 2, 5, 4, 7]
복잡도 분석
- 시간 복잡도: O(n) — 모든 요소를 정확히 한 번씩 순회합니다.
- 공간 복잡도: O(n) — 회전된 결과를 저장하기 위해 크기 n의 새로운 배열이 필요합니다.
참고: 제자리(in-place) 회전
추가 메모리 사용을 줄이고 싶다면 C++ 표준 라이브러리의 std::rotate(v.begin(), v.begin() + k, v.end())를 활용하거나, 배열 전체를 뒤집은 후 앞부분과 뒷부분을 각각 다시 뒤집는 역전(reversal) 알고리즘을 사용하여 O(1)의 추가 공간으로 제자리 회전을 구현할 수 있습니다.