원형 배열

원형 배열이란, 선형적인 배열의 마지막 인덱스가 첫 번째 인덱스와 논리적으로 연결되어 있다고 가정하여, 데이터가 마치 원형으로 배치된 것처럼 동작하게 만드는 자료구조이다.

나머지 연산자(%)를 사용하여 마지막 인덱스(N-1) 다음이 다시 0번째가 되도록 제어하는 것이다.

시계 방향: (현재 인덱스 + 이동하는 횟수) % N

반시계 방향: (현재 인덱스 - (이동하는 횟수 % N) + N) % N // 음수 방지

큐 회전 (인덱스 없이 해결)

큐를 이용하면 인덱스를 직접 계산할 필요 없이 문제를 해결할 수 있다.

앞에서 요소를 꺼내고(poll), 다시 뒤에 넣는(offer) 방식으로 자연스럽게 원형 구조를 시뮬레이션할 수 있다.

문제

백준 1158번 요세푸스

풀이 (원형 배열)

ArrayList와 같은 선형 자료구조에서는 오른쪽 이동을 할 때, 삭제를 하면 한칸씩 당겨지기 때문에 한칸 덜 가야 인덱스가 맞춰진다. (왼쪽 이동은 영향x)

삭제를 할 경우 나머지 연산을 할 때 전체 사이즈를 맞춰줘야 한다.

반복문안에서 list.remove()메소드 때문에 삭제하고 하나씩 앞으로 당겨오는 작업 $O(N)$ 발생

시간복잡도: $O(N^2)$

import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		List<Integer> list = new ArrayList<>();
		for(int i=1; i<=n; i++) {
			list.add(i);
		}
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		int idx = 0;
		while(!list.isEmpty()) {
			//삭제에 따른 인덱스 보정(-1)
			//전체 사이즈가 변동하니 list의 크기 이용
			idx = (idx + k - 1) % list.size();
			sb.append(list.remove(idx)); //제거
			if(!list.isEmpty()) sb.append(", ");
		}
		sb.append(">");
		System.out.println(sb);
	}
}

풀이 (큐)

모든 요소를 큐에 담는다.

큐에서 요소를 하나씩 뽑아 확인한다.

K번째가 아닌 요소는 다시 큐의 뒤에 담아 순서를 뒤로 미루고(회전),

K번째 요소는 다시 담지 않고 결과에 추가하여 제거한다.

큐가 빌 때까지 위 과정을 반복한다.

K번째가 될 때까지 큐를 회전시키고, 해당 요소만 제거하면 되므로 인덱스 연산(%) 없이도 동일한 결과를 얻을 수 있다.

총 N명의 사람을 제거해야 하므로 루프는 N번 실행, 매 회차당 K번 회전.

시간복잡도: $O(N·K)$

import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		Deque<Integer> q = new ArrayDeque<>();
		for(int i=1; i<=n; i++) {
			q.offer(i);
		}
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		int cnt=0;
		while(!q.isEmpty()) {
			int temp = q.poll();
			cnt++;
			if(cnt != k) {
				q.offer(temp);
			}
			else {
				sb.append(temp);
				if(!q.isEmpty()) sb.append(", ");
				cnt=0;
			}
		}
		sb.append(">");
		System.out.println(sb);
	}
}