LeetCode 189. Rotate Array

189.Rotate Array

문제

주어진 정수 배열 nums를 k번 만큼 rotate 하세요. k는 음수가 아님이 보장됩니다.

느낀점 또는 기타 정보

1. 소요시간: 4시간
2. 결국 풀지 못함, 하나의 케이스를 맞추면 다른 케이스가 깨지기를 반복
3. 배열의 reverse가 핵심 개념!

의사코드 또는 풀이 계획

1. 1차 시도 - 시간 초과

[1,2,3,4], k = 2 일 경우

1. nums[마지막인덱스] 값을 임시 변수에 저장.
2. 1, 2, 3 값을 한 칸씩 뒤로 복사해서 밀기
3. 임시 변수의 값을 가장 앞의 인덱스에 할당

2. leetcode 최다 투표 답안

[1,2,3,4,5,6,7], k = 3 일 경우

1. 0 ~ nums.length - 1까지 배열 뒤집기
	-> [7, 6, 5, 4, 3, 2, 1]
2. 0 ~ k - 1 까지 배열 뒤집기
	-> [5, 6, 7, 4, 3, 2, 1]
3. k ~ nums.length - 1까지 배열 뒤집기
	-> [5, 6, 7, 1, 2, 3, 4]

풀이

1. 시간 초과

class Solution {
    public void rotate(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
	        int lastEl = nums[nums.length - 1];	
            for (int j = nums.length - 2; j >= 0; j--) {
    	        nums[j + 1] = nums[j];
            }

            nums[0] = lastEl;
        }
    }
}

2.leetcode 최다 투표 답안

public void rotate(int[] nums, int k) {
	// k가 nums의 length 보다 클 경우가 생기기 때문에 k를 nums의 length로 나눈 나머지로 연산, 
    // k가 10, nums.length가 7인 경우에 7번 rotate는 결국 아무것도 안한 것과 같다. 따라서 3번만 rotate 시킨다.
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

// reverse 로직
public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}