[Codility] Lesson 2.1 - Cyclic rotation

Lesson 2 - 순환 회전(?)

• codility lesson 두번째 문제
• N개의 정수가 있는 배열 A가 있다고 할 때 배열의 회전(rotation)은 각 요소가 인덱스 하나만큼 오른쪽으로 이동하고 마지막 요소는 맨 처음으로 오는 것이다.
• 예를 들어, 배열 A = [3, 8, 9, 7, 6]의 회전은 [6, 3, 8, 9l 7] 이다.
• 목표는 배열 A를 K번 회전하는 것이다. 이 말은 A의 각 요소는 오른쪽으로 K번 이동할 것이라는 얘기다.
• N개의 정수가 있는 배열 A와 정수 K가 주어질 때 K번 회전한 배열 A를 반환하는 함수를 구현하라.

public int[] solution(int[] A, int K) {
	int[] rotatedArray = new int[A.length];
	
    for (int i = 0; i < A.length; i++) {
    	int newIndex = (i+K < A.length) ? i+K : (i+K)-A.length;
        rotatedArray[newIndex] = A[i];
    }
    return rotatedArray;
}

첫 풀이

• 결과로 반환할 새 배열을 만들고 거기에 인수로 받은 배열의 각 요소를 계산된 새 인덱스를 이용해 넣어 주면 될 것으로 생각
• 새 인덱스는 기본은 현재 인덱스에 K를 더한 결과(i+K), 그리고 그 값이 새 배열의 길이보다 크거나 같으면 현재 인덱스에 K를 더하고 소스 배열의 길이를 뺀 값
• 이렇게 만든 새 배열을 반환
• 기본 테스트 케이스는 통과하지만 엣지 케이스를 처리 안 해서 runtime error 발생

public int[] solution(int[] A, int K) {
	if (A.length == 0 || A.length == 1 || (A.length == K)) {
    	return A;
    }
    K = (K > A.length) ? K%A.length : K;
	int[] rotatedArray = new int[A.length];
	
    for (int i = 0; i < A.length; i++) {
    	int newIndex = (i+K < A.length) ? i+K : (i+K)-A.length;
        rotatedArray[newIndex] = A[i];
    }
    return rotatedArray;
}

두 번째 풀이

• 두 가지 실수
  • 엣지 케이스(argument인 A가 빈 배열이거나 요소가 하나 뿐이거나 A의 길이와 K가 같거나(모든 요소가 제자리로 옴) 처리
  • K가 배열 A의 길이보다 큰 경우를 처리해줘야 해서 K = (K > A.length) ? K%A.length : K 이 부분 추가, 나머지가 결국 실제 이동해야 할 거리이므로 위 계산식 사용
• 통과는 했지만 코드가 너무 지저분하다.

public int[] solution(int[] A, int K) {
    int[] rotated = new int[A.length];
    
    for (int i = 0; i < A.length; i++) {
        rotated[(i+k) % A.length] = A[i];
    }
    
    return rotated;
}

마지막

• 기본적으로는 첫번째 풀이와 비슷하고 결과 배열의 새 인덱스를 계산할 때 엣지케이스까지 처리할 수 있도록 했다.