[알고리즘 문제 풀이 스킬] 자바로 알고리즘에서 자주 사용되는 배열 shift 구현하기

알고리즘 문제를 해결하다 보면 문제와 무관한 부분에서 막힐 때가 있다.

오늘 알아볼 배열 shift도 비슷한 맥락이다.

배열 shift

문제 풀이에 배열 shift를 구현하라는 식으로 문제가 출제되지 않는다.

 

어떤 문제를 해결하려고 할 때, 다음과 같은 상황을 종종 마주했다.

아.. 거의 다 풀었는데 배열에 있는 애들이 왼쪽으로 5칸씩만 움직이면 끝인데,,

이 것은 실제로 본인이 프로그래머스 윈터 코딩 코테를 진행하면서 느꼈었던 감정이었다.

 

이 문제를 좀 더 명확히 이야기 해보자면 다음과 같다.

 

배열 A가 주어진 경우 왼쪽(오른쪽) 으로 n칸 shift 연산을 수행하라.

 

좀 더 쉽게 접근하기. hack !

배열 shift에도 hack이 존재한다.

 

에를 들어서 arr = [1, 2, 3, 4, 5] 라는 배열이 있고 오른쪽으로 3칸 이동하라고 가정해보자.

 

그럼 다음과 같은 과정을 거치게 된다.

하지만 배열 뒤집기를 이용 한다면 더욱 간단하게 할 수 있다.

 

배열 뒤집기

배열 뒤집기는 말 그대로 배열의 원소를 뒤집는 것이다.

 

arr = [1, 2, 3]

이라는 배열을 뒤집으면?

 

arr = [3, 2, 1]

이 되는 간단한 논리이다.

 

이런 배열 뒤집기를 이용할 것인데, 순서는 다음과 같다.

 

오른쪽 shift연산으로 n번 이동

1. 배열 0번째 인덱스에서 n번째 인덱스 까지 뒤집기
2. 배열 n번째 인덱스에서 배열 끝 인덱스 까지 뒤집기
3. 전체 배열 뒤집기.

왼쩍 shift 연산으로 n번 이동

1. 배열 끝 인덱스에서 n번째 까지 뒤집기
2. 배열 0번째 인덱스에서 배열 끝에서 n번째 를 뺸 만큼 뒤집기
3. 전체 배열 뒤집기

Java로 구현하기

이제 자바로 구현해보자.

전체 소스 코드를 먼저 보여주자면.

public class ArrayShift {
  public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int num = 3;

    rightShift(arr, num);
    System.out.println(Arrays.toString(arr));

    leftShift(arr, num);
    System.out.println(Arrays.toString(arr));
  }

  /* 배열 뒤집기를 위한 배열 인덱스끼리 변경 메서드 */
  private static void swap(int[] arr, int idx1, int idx2) {
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = arr[idx2];
  }

  /* 배열 시작 인덱스부터 끝 인덱스까지 반복을 돌며 swap을 진행할 메서드*/
  private static void reverse(int[] arr, int start, int end) {
    int end = end - 1; // 배열 마지막 인덱스는 배열 길이 - 1이기 때문에
    while(start < end) { // 반복을 (start ~ end) -> (start + 1 ~ end - 1) ... 까지 진행
      swap(arr, start, end);
      start++;
      end--;
    }
  }

  private static void rightShift(int[] arr, int n) {
    int size = arr.length;
    reverse(arr, 0, n);
    reverse(arr, n, size);
    reverse(arr, 0, size)
  }

  private static void leftShift(int[] arr, int n) {
    int size = arr.length;
    reverse(arr, size - n, size);
    reverse(arr, 0, size - n);
    reverse(arr, 0, size);
  }
}

위와 같다.

 

여기서 조금 헷갈릴 수 있는 메서드를 설명하자면

 

reverse

private static void reverse(int[] arr, int start, int end) {
  int end = end - 1;
  while(start < end) {
    swap(arr, start, end);
    start++;
    end--;
  }
}

• int end = end - 1; : 배열 마지막 인덱스는 배열 길이 - 1이기 때문에
• while(start < end) : 반복을 (start ~ end) -> (start + 1 ~ end - 1) ...을 start가 바꿀 end가 없을 때 까지 진행