[LeetCode]Rotate Array, JAVA 풀이

사용언어 : JAVA
난이도 :  Medium
문제 URL : https://leetcode.com/problems/rotate-array/
참조 책 : 쓰면서 익히는 알고리즘과 자료구조(91~100page)

 

1.문제

-문제설명

 입력으로 정수형 배열과 K 값이 주어지면, 각 요소를 우측으로 K번 이동 한다.

 단 k는 음수가 아니다.

 

-제약사항

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

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]

 

2.나의풀이

이 문제의 해결방법은 다음과 같다.

 

1. 입력과 같은 크기의 임시 배열(temp)를 생성한다.
2. 우측으로 이동 시킬 카운트를 구한다.
   - shiftCnt = k%nums.length
   - 크기가 7인 배열을 1000번 우측 이동 시켜도 결국 6번만 이동 시키면 된다.
3. .nums 배열을 순회한다.
   - 우측으로 이동 될 숫자들을 먼저 임시 배열(temp)에 넣는다.
   - nums배열의 처음부터 우측 이동되기 전까지의 값을 임시 배열(temp)에 넣는다.
4. 임시 배열(temp)를 nums 배열로 복사한다.

3.코드구현(JAVA)

위의 풀이방법으로 코드를 구현하면 아래와 같다.

class Solution {
    public void rotate(int[] nums, int k) {
    	int[] temp = new int[nums.length];
    	int shiftCnt = k%nums.length;
        int tempCnt = shiftCnt;

        // 쉬프트 될 숫자들을 temp 배열에 처음부터 넣는다.
    	for(int i=0; i<shiftCnt; i++) {
    		temp[i] = nums[temp.length-shiftCnt+i];
    	}
    	// 쉬프트 되고 남은 숫자들을 나머지 배열에 순차적으로 넣는다.
    	for(int i=0; i<nums.length-shiftCnt; i++) {
    		temp[tempCnt++] = nums[i]; 
    	}

        // nums배열에 다시 복사
    	for(int i=0; i<nums.length; i++) {
    		nums[i] = temp[i];
    	}
    }
}