2024.06.08 - Rotate-array

[wlsgh7608]

문제 - 링크

문제 풀이

• 주어진 배열을 오른쪽으로 K번 회전 했을 때의 결과를 보여주는 문제
  

1. 한 칸씩 이동

• 주어진 배열을 한 번 옮기는 코드
• 맨 마지막 element의 값을 저장하고 한 칸씩 옮긴 뒤 처음 element에 값 저장
• 이 것을 K번 만큼 반복
• 시간 복잡도 : O(N*K), 공간 복잡도 O(1)

            int tmp = nums[N - 1];
            for (int i = 1; i < N; i++) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;

2. 추가 배열을 사용

• 시간 복잡도 : O(1), 공간복잡도 : O(N)

    int N = nums.length;
    int[] temp = new int[N];
    for (int i = 0; i < N; i++) {
        temp[(i + k) % N] = nums[i];
    }
    
    for(int i = 0; i<N;i++){
        nums[i] = temp[i];
    }

3. 구간 별로 뒤집기

• 1. 먼저 전체를 뒤집음
• 2. k을 기준으로 블록을 나눠 각각 뒤집기
• 시간 복잡도 : O(N), 공간복잡도 : O(1)

코드

        int N = nums.length;
        k = k % N;

        reverse(nums, 0, N - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, N - 1);