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

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

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

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

c001

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

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

해당하는 배열과 시작점 s, 끝점 t 그리고 rotate 횟수인 k를 받는다.
Rotate하는 구간을 두 번 연속으로 새로운 배열 NEW_ARRAY에 복사한다.
NEW_ARRAY에서 복사가 시작되어야 하는 곳 new_s = NEW_ARRAY.length – ((t-s+1) % k)로 구한다.
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; 
  } 
}

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

c002

잘 되는 것 같네요.^^

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

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

Related

Leave a Reply Cancel reply