참고
문제해설
NOTE
•
입력 값 ⇒ 정수 배열, 몇번 회전해야하는지에 대한 정수
•
출력 값 ⇒ 회전을 마친 정수 배열
•
O(1)의 방식으로 도전해볼것이며, 다양한 해결책이 있다고 한다.
문제 로직고민
NOTE
•
정수 배열을 어떻게하면 회전시킬 수 있는가?
◦
회전하는 만큼 시작 idx를 추가했다.
◦
ex) 배열의 크기가 5, 회전이 2, 넣어야하는 idx 0
⇒ (5 - 2 + 0) % 5 ⇒ idx 3
◦
idx0을 시작점으로 idx3부터 값을 순서대로 넣으면된다.
•
위의 방식으로하면 순환하는동안 배열이 변경되는 문제가 있다.
◦
기존 배열을 변경하면서 진행하므로 예상하지 못한값이 나올 확률이 크다.
◦
새로운 배열에 값을 옮기고 기존 배열을 덮어쓰는 방식으로 진행한다.
작성코드
NOTE
class Solution {
public void rotate(int[] nums, int k) {
int[] nums2 = new int[nums.length];
int rotate = k % nums.length;
for(int i = 0; i < nums.length; i++){
int idx = (nums.length - rotate + i) % nums.length;
nums2[i] = nums[idx];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = nums2[i];
}
}
}
Java
복사
이전 문제처럼 O(1)은 달성하지 못했지만, 해결은 되었다.
•
기존 배열하나만 가지고 회전시키는 로직을 생각하지 못해 일단 새로운 배열을 추가해 진행했다.
정답코드
NOTE
public void rotate(int[] nums, int k) {
int len = nums.length;
k = k%len;
//2. reverse 이용
reverse(nums,0,len-1); //step1 전체 reverse [7,6,5,4,3,2,1]
reverse(nums,0,k-1); //step2 로테이션 숫자들 reverse [ 5,6,7,4,3,2,1 ]
reverse(nums,k,len-1); //step3 나머지 숫자들 reverse [ 5,6,7,1,2,3,4 ]
}
public void reverse(int[] nums, int start, int end){
while(start < end){
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
하나의 배열로 진행하는 방법으로, reverse 메서드를 활용하는 방식이 존재했다.
•
이 방식으로 하면 하나의 배열로, 한번의 순회에 배열을 회전시킬 수 있다.