배열의 회전 (쓰면서 익히는 알고리즘 자료구조 p.91)

1.10 배열의 회전

• 문제링크  : (6) Rotate Array - LeetCode

📌 Problem

• 정수형 배열과 k값이 주어지면 각 요소를 우측으로 k 번 이동 및 회전을 함. 
• k는 양의 정수 값

• Given an array, rotate the array to the right by k steps, where k is non-negative.
• Example 1:
  • Input: nums = [1,2,3,4,5,6,7], k = 3
  • Output: [5,6,7,1,2,3,4]
  • Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
• Example 2: 
  • Input: nums = [-1,-100,3,99], k = 2
  • Output: [3,99,-1,-100]
  • Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

 

• •  

📝 Solution

 

class Solution {
    public void rotate(int[] nums, int k) {
        int count =0;
        for(int i =0; i < nums.length; i++){
            if (count>= nums.length){
                return;
            }
            int curr = i;
            int prev = nums[i];
            
            while(true){
                int next = (curr + k) % nums.length; 
                int temp = nums[next];
                nums[next]=prev;
                prev= temp;
                
                curr=next;
                count+=1;
                
                if(curr == i){
                    break;
                }
                
            }
        }
    }
}

• Time complexity : O(n)
• 모든 요소가 한번씩 교환이 될 때까지 배열을 순회한다.
• 요소를 k만큼 이동 및 저장한다
•  이동한 위치의 이전요소는 저장한다.
• 저장한 요소는 다음 k만큼 이동하여 넣는다.
• 시작한 요소까지 값을 이동시키면 해당 순회를 종료한다.
• 이동시킬 때마다 카운트한다
• 다음요소를 선택하고 다시 2번의 내용을 반복한다