LeetCode 189번 Rotate Array
LeetCode 189번 Rotate Array

목차

문제 문제 링크

정수 배열 `nums`가 주어지고, 정수 `k`가 주어질 때, 배열을 오른쪽으로 `k`번 회전하세요.

입력

정수 배열 `nums`와 정수 `k`가 주어집니다.

예제 입력 1

nums = [1,2,3,4,5,6,7], k = 3

출력

배열을 오른쪽으로 `k`번 회전한 결과를 반환합니다.

예제 출력 1

[5,6,7,1,2,3,4]

풀이

문제 해결 방법

이 문제는 배열을 회전하는 문제입니다. 주요 해결 방법은 다음과 같습니다:

  1. 추가 배열을 사용하는 방법:
    • 새로운 배열을 만들어 회전된 결과를 저장
    • 시간 복잡도: O(N), 공간 복잡도: O(N)
  2. 순환 이동을 사용하는 방법:
    • 배열을 순환적으로 이동
    • 시간 복잡도: O(N*k), 공간 복잡도: O(1)
  3. 세 번 뒤집기를 사용하는 방법:
    • 전체 배열을 뒤집고, 앞부분과 뒷부분을 각각 뒤집기
    • 시간 복잡도: O(N), 공간 복잡도: O(1)

세 번 뒤집기 방법의 시간 복잡도는 O(N)이고, 공간 복잡도는 O(1)입니다.

코드

class Solution {
public:
    void rotate(vector& nums, int k) {
        int n = nums.size();
        k = k % n; // k가 배열 길이보다 클 경우 처리
        
        // 전체 배열 뒤집기
        reverse(nums.begin(), nums.end());
        // 앞부분 k개 뒤집기
        reverse(nums.begin(), nums.begin() + k);
        // 뒷부분 n-k개 뒤집기
        reverse(nums.begin() + k, nums.end());
    }
};