Rotate Array - 리트코드

https://leetcode.com/problems/rotate-array

평가

결과 : 2번 실패 후 성공
풀이시간 : 15분

시간을 더 줄일 수 없나 고민해봤는데 불가능한 것 같습니다.

제 풀이에서 시간복잡도는 선형복잡도인데 이보다 더 시간을 줄이려면 Log 시간복잡도가 되어야 합니다. 그건 불가능한 것 같습니다.

아마 저보다 빠른 풀이들은 stack의 크기가 k가 아닌 nums.length - k일 겁니다.
예시에 따라 차이가 있다 분이지, 시간복잡도는 똑같기 때문에 무의미하다고 생각해 그냥 넘어가도록 하겠습니다. 추후 다른 분들의 풀이를 보고 판단하도록 하겠습니다.

1번째 실패 원인

nums.length < k 엣지 케이스를 처리하지 않았습니다.
아예 문제를 생각 못했으면 어쩔수 없는 건데, 수도코드에 해당 부분을 적어두고도 못보고 풀었습니다. 이런 실수는 정말 자제해야 합니다.

2번째 실패 원인

nums.length < k 엣지 케이스에서 % 연산을 해야 하는데 / 연산을 했습니다. 마음이 급했습니다.

아이디어

아이디어는 다음과 같습니다.

• nums를 딱 한 번만 회전시킵니다.
  예를 들어 nums의 크기가 5, k가 11이라면 두 바퀴 돌고 한 칸 이동한 게 됩니다. 즉, nums의 크기에서 k를 mod 연산하면 됩니다.

• k만큼 회전한다면 k의 크기만큼 임시 저장소(stack)에 넣습니다.

• nums.length - k 개를 k 칸 앞으로 이동시킵니다.

• stack에서 데이터를 꺼내어 빈 칸에 넣어줍니다.

(그림)

수도코드

// 여러 바퀴를 회전하는 경우, 마지막 바퀴만을 계산한다.
if nums.length < k:
  k %= nums.length

Stack stack;

// [1,2,3,4,5], k==3일 때 -> 스택에 5,4,3을 담는다
for(k회):
  stack.push(nums.length - 인덱스);

// 1,2 를 3칸(k) 민다.

// 1,2,3 위치에 3,4,5를 넣는다
idx = 0;
for(k회);
  nums[idx++] = stack.pop();

정답 코드

• Stack 자료구조는 속도가 느려(sync 이슈) 배열로 변경했습니다.
  코테상에서 큰 차이는 없는데 그냥 변경했습니다.

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length < k) {
            k %= nums.length;
        }

        // 정상 케이스
        int[] stack = new int[k];
        for(int i=0; i<k; i++) {
            stack[k - 1 - i] = nums[nums.length - 1- i];
        }

        for(int i=nums.length - k - 1; i>=0; i-- ) {
            nums[i+k] = nums[i];
        }


        for(int i=0; i<stack.length;i++) {
            nums[i] = stack[i];
        }
    }
}