저번에 포스팅한 rotate Array와 비슷한 문제를 풀어보았다.
practice.geeksforgeeks.org/problems/rotate-array-by-n-elements/1#
Rotate Array | Practice | GeeksforGeeks
practice.geeksforgeeks.org
문제
Given an array of size N. The task is to rotate array by D elements where D ≤ N.
Example 1:
Input:
N = 7
Arr[] = {1, 2, 3, 4, 5, 6, 7}
D = 2
Output: 3 4 5 6 7 1 2
Explanation:
Rotate by 1: [2, 3, 4, 5, 6, 7, 1]
Rotate by 2: [3, 4, 5, 6, 7, 1, 2]
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 105
1 ≤ Arr[i] ≤ 1000
0 ≤ D ≤ N
코드
package rotate;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.Collectors;
public class ReversalRotateArray {
public static void leftRotate(Integer[] arr, int n, int d) {
int temp = arr[0];
int[] tempArr = new int[n];
int index = 0, count = 0;
if(n==d) return;
for (int i = d; count < n; i++, count++) {
tempArr[count] = arr[i%n];
}
count = 0;
while (index < n) {
if (index < n-d) {
temp = arr[index];
arr[index] = tempArr[index];
tempArr[index] = temp;
count++;
}
if (index >= n-d) {
arr[index] = tempArr[count++];
}
index++;
}
}
public static void printArray(Integer[] arr) {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < arr.length; i++) {
if (i == arr.length - 1) {
stringBuilder.append(arr[i] + "]");
break;
}
stringBuilder.append(arr[i] + ", ");
}
System.out.println(stringBuilder.toString());
}
public static void main(String[] args) {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
try {
int n = Integer.parseInt(bufferedReader.readLine());
Integer[] arr = new Integer[n];
Arrays.stream(bufferedReader.readLine().split(" ")).map(s -> Integer.parseInt(s))
.collect(Collectors.toList()).toArray(arr);
int d = Integer.parseInt(bufferedReader.readLine());
leftRotate(arr, n, d);
printArray(arr);
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
처음에는 당연히 저번에 풀었던 방식으로 비슷하게 풀어보았지만.
내 코드의 불합리함에 절망해버렸다. 시간을 줄이기 위해 여러 자료구조를 사용하는 방법이 생각났지만, 이 챕터에서는 아직 다른 자료구조를 배우지 않은 상태임으로, 좀 더 고집을 부려보기로 했다.
하지만, 코드를 보던 중, n==d일때의 경우를 생각해보았다. 결국에는 1,2,3,4,5,6,7의 배열이 주어질 경우, rotate를 수행하여도, 1,2,3,4,5,6,7의 결과를 보이기 때문에, 이 조건식만 추가해 보았다.
public static void leftRotate(Integer[] arr, int n, int d) {
int temp = arr[0];
int[] tempArr = new int[n];
int index = 0, count = 0;
if(n==d) return;
for (int i = d; count < n; i++, count++) {
tempArr[count] = arr[i%n];
}
count = 0;
while (index < n) {
if (index < n-d) {
temp = arr[index];
arr[index] = tempArr[index];
tempArr[index] = temp;
count++;
}
if (index >= n-d) {
arr[index] = tempArr[count++];
}
index++;
}
}
내가 practice를 자랑스럽게 풀어보았음으로, 문제에서는 어떻게 풀었는지 확인해 보았다.
예제로 나온 코드
// Java program for reversal algorithm of array rotation
import java.io.*;
class LeftRotate {
/* Function to left rotate arr[] of size n by d */
static void leftRotate(int arr[], int d)
{
if (d == 0)
return;
int n = arr.length;
// in case the rotating factor is
// greater than array length
d = d % n;
reverseArray(arr, 0, d - 1);
reverseArray(arr, d, n - 1);
reverseArray(arr, 0, n - 1);
}
/*Function to reverse arr[] from index start to end*/
static void reverseArray(int arr[], int start, int end)
{
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
/*UTILITY FUNCTIONS*/
/* function to print an array */
static void printArray(int arr[])
{
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = arr.length;
int d = 2;
leftRotate(arr, d); // Rotate array by d
printArray(arr);
}
}
/*This code is contributed by Devesh Agrawal*/아, 저렇게도 풀수 있구나..
N=7, arr=[1,2,3,4,5,6,7], D=2일 경우
reverseArray(arr, 0, 2- 1);
// [1,2,3,4,5,6,7] → [2,1,3,4,5,6,7]
reverseArray(arr, 2, 6);
// [2,1,3,4,5,6,7] → [2,1,7,6,5,4,3]
reverseArray(arr, 0, 6);
// [2,1,7,6,5,4,3] → [3,4,5,6,7,1,2]
진행된것을 보았는데도 신박한 느낌이다.
결과도 한 번 봐볼까?
결과
😒 input data 적용은 저번 코드를 그대로 참고했다.
🤔 그리고 Example2가 문제에 명시되어있는데 예상되는 결과가 실제 코드에서 수행되는 결과와 다르다.
🤢 Example2를 보고, 아! d+1==n 이면 rightRotate가 수행되는건가 하면서, 코드를 수정해보았지만 웬걸, 시간낭비만 했다.
😜 Example2는 왜 두신거죠? 스앵님
* 위에서 제시한 코드 이외에도 여러 방법이 나와있고, 각각 친절하게 원리와 시간복잡도 및 공간복잡도가 명시되어있으니 필요하면 직접 사이트에서 봐보는것을 추천한다.
www.geeksforgeeks.org/array-rotation/
Program for array rotation - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org