[Algorithm/Swift] Codility / CyclicRotation

문제

https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

풀이

배열 A를 오른쪽으로 K번 이동시킵니다.

배열의 마지막 요소는 배열의 첫 번째 위치로 이동합니다.

Troubleshooting

• runtime error이 발생하여 O(N)의 복잡도를 가진 .insert()를 바꾸기로했다.
  • .append는 O(1)이기에 변경해준다.

Tip

• 마지막 배열의 요소 값을 제거하거나 가져오는 방법 O(1)의 복잡도를 가진다.
  
  • array.popLast() / removeLast() 
• 순서를 변경해주는 reserved()는 O(1)의 복잡도를 가진다.

Code

public func solution(_ A : inout [Int], _ K : Int) -> [Int] {
    
     var emptyArray = A 
 
     for _ in 0..<K {
         let lastEle = emptyArray.popLast()!
         emptyArray.insert(lastEle, at:0)
     }
     
    return emptyArray
}

Code

public func solution(_ A : inout [Int], _ K : Int) -> [Int] {

   var emptyArray = A

   for _ in 1...K {
       let arrayLastNum = emptyArray.popLast()!
       emptyArray = emptyArray.reversed()
       emptyArray.append(arrayLastNum)
       emptyArray = emptyArray.reversed()
   }
   
   return emptyArray
}

여전히 87%였다...런타임 에러를 보고 성능 문제라고 생각했는데 Correctness의 문제였다.......

 

public func solution(_ A : inout [Int], _ K : Int) -> [Int] {
    
   var emptyArray = A

   if emptyArray.count <= 1 || emptyArray.min() == emptyArray.max() {
     
     return emptyArray
   }

   for _ in 0..<K {
       let arrayLastNum = emptyArray.popLast()!
       emptyArray = emptyArray.reversed()
       emptyArray.append(arrayLastNum)
       emptyArray = emptyArray.reversed()
   }
   
   return emptyArray
}

배열의 요소를 체크하는 로직을 넣어준다.

100% 달성 !

하지만 ! 

Algorithm 의 정석은 이렇게 하네요..

public func solution(_ A : inout [Int], _ K : Int) -> [Int] {

	var empArray = Array(repeating: 0, count: A.count)
    
    for i in 0..<A.count {
        empArray[(i+K) % A.count] = A[i]
    }
    
    return empArray
}

원리는 이렇습니다.

배열의 요소를 옆으로 K번 이동시키는게 아니라 처음부터 K번 위치에 값을 넣어주는 것입니다.

 

배열을 A 배열의 카운트만큼 동일하게 만들어줍니다.

A 요소의 위치를 몇번째 움직일 칸을 더해준후 배열의 카운트의 나머지값을 구하면 다음 위치를 알 수 있습니다.

해당 위치의 요소의 값을 넣어주면 됩니다.

 

알고리즘은 이렇게 푸는게 맞는것 같아요.. ㅎ