문제로 풀어보는 알고리즘 0.3 생각해보기 풀이 첫 번째 문제

By | 2012/08/31

  인사이트에서 재미있는 행사를 합니다.

코딩 인터뷰에 대처하는 개발자의 자세

  해당 글을 보시면 그 곳에서 발간한 책에 나오는 문제를 블로그에 풀이를 올리면 추첨을 통해 상품을 준다고 합니다. 상품이 상당히 geek한 것 같아 별 관심이 가지는 않았지만 그래도 문제 자체가 흥미롭기에 풀어보았습니다.

 

c001

  위와 같은 문제입니다. 배열 안에 Subarray를 rotate 시키는 문제입니다. 이런 문제를 어디서 접해본 것 같지만, 그냥 넘어가겠습니다.

  이를 풀기 위해 좋은 아이디어/알고리즘이 있을 것입니다. 하지만 저라면 이렇게 풀겠습니다.

  1. 해당하는 배열과 시작점 s, 끝점 t 그리고 rotate 횟수인 k를 받는다.
  2. Rotate하는 구간을 두 번 연속으로 새로운 배열 NEW_ARRAY에 복사한다.
  3. NEW_ARRAY에서 복사가 시작되어야 하는 곳 new_s = NEW_ARRAY.length – ((t-s+1) % k)로 구한다.
  4. NEW_ARRAY에서 new_s 구간부터 t-s+1만큼 기존의 배열의 s점에서부터 복사시킨다.

  이를 구현한 것이 다음 Java 코드입니다.

import java.util.Arrays;

public class Insight_Problem_01
{
  public static void main(String[] args) throws Exception
  {
    int[] target_array_01 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int s = 2;
    int t = 6;
    int k = 1;
   
//    First Test Case
//    Example in blog post
    System.out.println("First Test Case");
    System.out.print("Original Array" + "\t\t\t\t");
    System.out.println(Arrays.toString(target_array_01));
    System.out.print("Rotated Array with s: " + s + ", t: " + t + ", k: " + k + "\t");
    System.out.println(Arrays.toString(k_right_rotate_array(target_array_01, s, t, k)));
   
//    Second Test Case
//    Change the k from 0 to target_array_01.length
    System.out.println("\n\nSecond Test Case");
    System.out.print("Original Array" + "\t\t\t\t");
    System.out.println(Arrays.toString(target_array_01));
    for(k = 0 ; k <= target_array_01.length ; k++)
    {
      System.out.print("Rotated Array with s: " + s + ", t: " + t + ", k: " + k + "\t");
      System.out.println(Arrays.toString(k_right_rotate_array(target_array_01, s, t, k)));
    }

//    Third Test Case
//    Target Array's size is one
    int[] target_array_02 = new int[]{1};
    s = 0;
    t = 0;
   
    System.out.println("\n\nThird Test Case");
    System.out.print("Original Array" + "\t\t\t\t");
    System.out.println(Arrays.toString(target_array_02));
    for(k = 0 ; k <= target_array_02.length ; k++)
    {
      System.out.print("Rotated Array with s: " + s + ", t: " + t + ", k: " + k + "\t");
      System.out.println(Arrays.toString(k_right_rotate_array(target_array_02, s, t, k)));
    }
  }
 
  /*
   * Right rotate the sub array from s to t by k times
   * origin_array: original array
   * s: subarray's staring point
   * t: subarray ending point
   * k: rotate times
   *
   * Return: Array that is rotated in subarray
   * */
  private static int[] k_right_rotate_array(int[] origin_array, int s, int t, int k)
  {
//    Test argument
    if(s < 0 &&
      s >= origin_array.length &&
      t < 0 &&
      t >= origin_array.length &&
      k < 0 &&
      s > t &&
      origin_array.length <= 0)
    {
      System.err.println("Please check arguments of k_right_rotate_array function in Insight_Problem_01 class");
    }
   
//    Make new array
    int target_array[] = new int[origin_array.length];
    System.arraycopy(origin_array, 0, target_array, 0, origin_array.length);
   
//    Make new array to copy from s to t two times
    int temp_array_size = t - s + 1;
    int[] temp_array = new int[temp_array_size*2];
    System.arraycopy(target_array, s, temp_array, 0, temp_array_size);
    System.arraycopy(target_array, s, temp_array, temp_array_size, temp_array_size);
   
//    Find start point from new array
    int new_start_point = temp_array_size - (k % temp_array_size);
   
//    Assign the new array to original array
    System.arraycopy(temp_array, new_start_point, target_array, s, temp_array_size);
   
//    Return it
    return target_array;
  }
}

c5

  이 코드의 수행 결과입니다.

c002

  잘 되는 것 같네요.^^

  참고로 만약 왼쪽으로 rotate하고 싶으면 new_s = NEW_ARRAY.length – ((t-s+1) % k) 대신 new_s = (t-s+1) % k으로 하면 되더군요.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.