회전 알고리즘

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• d가 1인 경우, 정방향 d가 2인 경우 역방향으로 배열의 원소에 대해 위치(index)를 회전해야 함
• 여기서 x의 위치를 0번 인덱스에서 시작해서 계속해서 회전한 결과의 위치를 기준으로 그 다음 회전을 해야 하므로,
• x의 위치를 계속해서 바꿔줘야 하는 점에 유의해야 함
• 또, y의 입력 범위가 100이하 이므로 n으로 나눈 나머지를 다시 y에 할당하게 되면 반복되는 주기를 없앨 수 있음
• 위 조건을 만족하면서 정방향의 경우에는 x + y가 n보다 크거나 같은 경우, 배열의 오른쪽 끝을 벗어나게 되므로 n을 다시 빼주고, 작은 경우에는 그 만큼 회전하면 되고,
• 역방향의 경우에는 x - y 가 0보다 작은 경우 배열의 왼쪽 끝을 벗어나게 되므로 n을 더해주고, 크거나 같은 경우에는 그 만큼 회전하면 됨
• 따라서 각 q개의 질문에 대한 회전은 O(1)의 시간복잡도로 해결할 수 있음

5. 전체 코드

//MARK: - 회전 알고리즘

//MARK: - Framework
import Foundation

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    let n: Int = input.map { Int($0) }[0] ?? 0
    let q: Int = input.map { Int($0) }[1] ?? 0
    
    guard let inputA: [String] = readLine()?.components(separatedBy: " ") else { return }
    let a: [Int] = inputA.map { Int($0) ?? 0 }
    var x: Int = 0
    var answer: String = ""
    
    
    //MARK: - Process & Output
    for _ in 0..<q {
        guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
        let d: Int = inputData.map { Int($0) }[0] ?? 0
        var y: Int = inputData.map { Int($0) }[1] ?? 0
        y = y >= n ? y % n : y
        
        switch d {
        case 1:
            x = x + y >= n ? x + y - n : x + y
        case 2:
            x = x - y < 0 ? n + (x - y) : x - y
        default:
            break
        }
        
        answer += "\(a[x])\n"
    }
    
    print(answer)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.