[hackerrank 문제 풀이] Circular Array Rotation

Junu Kim·2025년 11월 21일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

41/46

[Queue] Circular Array Rotation

난이도: ★☆☆☆☆ • solved on: 2025-11-17

문제 요약

문제 유형: 배열 회전, 인덱스 변환
요구사항: 길이 N 배열을 오른쪽으로 K번 회전한 뒤, queries에 주어진 인덱스의 값을 출력해야 한다.

사용 개념

자료구조
- Queue(ArrayDeque)
- 배열(List, Integer[])
알고리즘/기법
- 모듈러(modulo) 기반 회전 최적화
- 인덱스 변환(index mapping)
핵심 키워드
- rotation
- modulo
- index calculation

풀이 아이디어 및 코드

방법 1 : Queue를 사용한 직접 회전 방식

문제 분해

배열의 모든 값을 Queue에 담는다.

k % n 만큼만 회전하면 충분하므로 이를 이용한다.

오른쪽 회전을 queue 방식(pop→push)과 반대 방향으로 구현하기 위해 (n - shift)번 pop→push한다.

Queue를 배열로 변환한 뒤, query 인덱스의 값을 반환 리스트에 담는다.
핵심 로직 흐름
queue ← a 저장
shift = k % n
queue를 (n - shift)번 pop→push
queue 값을 arr 배열에 저장
각 query 인덱스의 arr 값을 result에 추가
예외 처리

shift = k % n 처리로 불필요한 회전을 방지한다.

public static List<Integer> circularArrayRotation(List<Integer> a, int k, List<Integer> queries) {
    // Write your code here
    Queue<Integer> queue = new ArrayDeque<>();
    Integer[] arr = new Integer[a.size()];
    List<Integer> result = new ArrayList<>();
    for(int i = 0; i<a.size(); i++){
        queue.add(a.get(i));
    }
    for(int i = 0; i<a.size() - (k%a.size()); i++){
        queue.add(queue.poll());
    }
    
    
    for(int i = 0; i<a.size(); i++){
        arr[i] = queue.poll();
    }
    
    for(int item: queries){
        result.add(arr[item]);
    }
    
    return result;
}

방법 2 : 회전 없이 인덱스 변환만 수행하는 O(1) 접근

문제 분해

중요한건 인덱스의 변화이기 때문에 실제 배열을 물리적으로 회전할 필요가 없다.

오른쪽 회전된 배열에서 query 인덱스 j는 원본 배열의 (j - shift + n) % n 위치와 동일하다.

이 식을 통해 즉시 값을 꺼낼 수 있다.
핵심 로직 흐름
shift = k % n
for each query j:
    index = (j - shift + n) % n
    result.add(a[index])
예외 처리

(j - shift)가 음수일 수 있으므로 +n 후 %n 처리한다.

public static List<Integer> circularArrayRotation(List<Integer> a, int k, List<Integer> queries) {
    int n = a.size();
    int shift = k % n;
    List<Integer> result = new ArrayList<>();

    for (int q : queries) {
        int index = (q - shift + n) % n;
        result.add(a.get(index));
    }

    return result;
}

시간·공간 복잡도

방법 1

시간 복잡도: O(N + K)

공간 복잡도: O(N)

방법 2

시간 복잡도: O(Q)

공간 복잡도: O(1)

어려웠던 점

회전 방향을 처음 반대로 이해하여 잘못 구현했다.
- 문제에서 요구했던 회전 : 맨 뒤의 원소를 맨 앞으로 옮긴다
- 내가 했던 회전 : 맨 앞의 원소를 맨 뒤로 옮긴다
Queue의 회전 방향과 문제에서 요구하는 방향이 달라서 k % n을 고려해야 함을 깨닫는 데 시간이 걸렸다.
- 처음에는 k만큼 실제로 회전했다.
Queue를 이용한 회전은 직관적이지만 성능이 좋지 않다는 점을 확인했다.
- 중요한건 인덱스다