Array - Rotate Array

 

https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/

Explore - LeetCode

 

Note : 

• 오른쪽으로 k 만큼 회전시켜라. 
• in-place로 해 보라.

 

Try1. 추가 메모리 사용 ... 할만 하지만 in-place가 아니다. 

int[] arrOut = new int[ nums.Length ]; 
for(int q = 0; q < nums.Length; ++q)
{
	if(q+k >= nums.Length)
	{
		arrOut[q+k-nums.Length] = nums[q];
	}
	else arrOut[q + k] = nums[q];
}
for(int q = 0; q < arrOut.Length; ++q)
	nums[q] = arrOut[q];

 

Try2. in-place... 뒤쪽에서 계산해서 하나씩 당기로 그 뒤로 한칸씩 밀음을 반복.

 - 아이디어는 나쁘지 않으나, 시간초과로 실패.

k = (k%nums.Length);
int left = 0;
for(int idx = nums.Length-k; idx < nums.Length; ++idx)
{
  // move this to 1st place.
  int temp        = nums[ left ];
  nums[ left ]    = nums[idx];
  // push this to right.
  for(int n = idx; n > left; --n)
  {
  	nums[ n ]   = n-1==left ? temp : nums[n-1];
  }
  ++left;
}

 

Try3. in-place.. 

 전체를 뒤집고, 구간을 뒤집는 방법. .. 이건 성공.

{
  k = (k%nums.Length);
  Reverse(nums, 0, nums.Length);
  Reverse(nums, 0, k);
  Reverse(nums, k, nums.Length-k);
}
void Reverse(int[] array, int idxLeft, int length)
{
  for(int q = 0; q < length; ++q)
  {
    int idxL    = idxLeft + q;
    int idxR    = idxLeft+length-q-1;
    if(idxL >= idxR)
    	break;
    int temp    = array[idxL];
    array[idxL] = array[idxR];
    array[idxR] = temp;
  }
}

 

Retro 

• 우연히 찾아야 하는가, 직관이 그만큼 좋아야 하는가. 아니면 외워야 하는가. 
• 늘 고민하는 이슈에 봉착. 솔루션을 어느정도 외워야 함은 고민의 영역이 아닌 필수인 듯 하다. 이틀 고민해서 솔루션을 만드는 것은, 10분안에 풀어야 하는 면접 풀이에게는 효과가 없을 듯 하다.
• 직관에 의한 알고리즘을 만들었을때, 이 솔루션을 어떻게 검증해야 하는가. 일부의 input을 통과시켰다고 해서, 모든 것들에 제대로 작동하는지는 어떻게 확인하는가.