[ LeetCode | Java ] 189. Rotate Array

dokim·2023년 8월 25일

[LeetCode] Top 150 leetcode

[LeetCode] Top Interview 150

목록 보기

9/51

🏷️189. Rotate Array

1. 문제 설명

정수 배열 nums가 주어지면 배열을 k 단계만큼 오른쪽으로 회전합니다. 여기서 k는 음수가 아닙니다.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 10^5
2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

2. 접근 방식

방법 1) 실패

Example 1을 보면k=3 만큼 뒷부분 숫자 [5, 6 ,7]가 앞으로 옮겨지고, nums.length-k만큼의 앞부분 숫자 [1, 2, 3, 4] 가 뒤로 옮겨지면 원하는 결과값이 나옵니다. 즉, 결과적으로 위치를 바꾸어야할 앞부분, 뒷부분 숫자 범위를 찾아 바꾸어주면 원하는 결과값을 도출 할 수 있다고 생각하였습니다.

실패 원인 : 하지만 입력값이 nums = [-1], k = 2인 경우, nums = [1, 2], k = 2인 경우경우 원하는 Rotate 값은 반환하지 못합니다.

구현 코드

      class Solution {
          public void rotate(int[] nums, int k) {

              int len = nums.length;
              if (len == k || len == 1)
                  return ;

              // 이동해야 하는 앞부분 숫자 복사
              int[] tmp = Arrays.copyOf(nums, len - k);

              // 이동해야 하는 뒷부분 숫자 앞으로 옮기기 
              for(int i = 0; i < k; i++){
                  nums[i] = nums[len - k + i];
              }

              // 복사한 앞부분 숫자를 붙여주기
              for(int i = k; i < len; i++){
                  nums[i] = tmp[i-k];
              }
          }
      }

방법 2) 실패

List를 활용하여 마지막 데이터를 index 0에 추가하고 삭제하는 방식으로 데이터를 가공하였습니다. 그리구 마지막에 sums에 list의 데이터로 초기화하여 결과값을 얻었고, 이전에 발생한 에러를 잡았습니다.

실패 원인 : 하지만 Time Limit Exceeded에러로 시간초과 에러가 발생하였습니다.

구현 코드


import java.util.Arrays;
			import java.util.List;

			class Solution {
  public void rotate(int[] nums, int k) {

      int len = nums.length;
      List<Integer> list = new ArrayList<>();

      // list를 sums데이터로 초기화
      for (Integer num : nums) {
          list.add(num);
      }

      while(k-- > 0){
          list.add(0, list.get(len -1)); //첫번재 index에 nums 마지막 index 정수 추가
          list.remove(len); // nums 마지막 index 정수 삭제
      }

      // sums에 가공한 list 데이터로 초기화
      for(int i = 0; i < len; i++){
          nums[i] = list.get(i);
      }

       System.out.println(list);
  }
			}

방법 3) 성공

다른 방법을 생각해 보다가 처음부터 다시 생각하게 되었습니다. 방법1에서 기본 예시를 통과하고 다른 예시가 문제가 되었습니다. nums = [-1], k = 2인 경우, nums = [1, 2], k = 2인 경우경우를 다르게 예외처리할 방법이 없을까 생각하게 되었고, 간단히 2줄의 조건문을 넣어 쉽게 해결하게 되었습니다. nums배열의 길이가 k보다 짧은 경우 rotate가 nums길이/k만큼 발생하므로 초반에 조건문을 걸고 k = k % nums.length하여 불필요한 rotate를 줄이도록 하였습니다.

3. 의사 코드


	if(nums 배열의 길이가 k보다 작은경우)
    	k = k % nums.length

	
    int[] tmp = nums에서 이동해야 하는 앞부분 숫자를 복사
    
        for()
        	nums[앞부분 index] = nums[옮겨야할 뒷부분 숫자]
        
        for(){
            nums[뒷부분 index] = tmp[앞부분에 있던 숫자 붙이기]
        }

4. 구현 코드

class Solution {
    public void rotate(int[] nums, int k) {
            
        int len = nums.length;
        if( k > len )
            k =  k % len; 

        // 이동해야 하는 앞부분 숫자 복사
        int[] tmp = Arrays.copyOf(nums, len - k);

        // 이동해야 하는 뒷부분 숫자 앞으로 옮기기 
        for(int i = 0; i < k; i++){
            nums[i] = nums[len - k + i];
        }

        // 복사한 앞부분 숫자를 붙여주기
        for(int i = k; i < len; i++){
            nums[i] = tmp[i-k];
        }
    }
}

시간 복잡도: O(n)
공간 복잡도: O(n)
- 배열 tmp을 사용하여 최대 n개를 저장하기 때문에 그렇습니다.

5. 최종 회고

다양한 방법으로 시도했지만 다른 케이스에서 발생하는 에러 때문에 오랜 시간이 걸린 문제였습니다. 문제를 더 정확하게 이해하려고 노력했지만 조금 더 다른 예외가 발생하지 않는지, 시간복잡도와 공간복잡도에 대해 생각해보고 문제에 접근하고자 합니다.
문제를 제대로 이해했지만 조금 더 잘 활용할 수 있게 접근법을 더 생각을 해보는 것이 좋을 것 같습니다.