[BOJ] 1021: 회전하는 큐 (JAVA)

1021번: 회전하는 큐

 

풀이

 

내가 푼 방법은 BFS로 최단거리를 기록해준 다음, 해당 최단거리를 더해주는 방식이다.

 

이렇게 연결리스트인 경우 나머지(%, mod)로 문제를 접근하면 좀 더 쉽게 접근할 수 있다.

 

1부터 N까지 숫자가 존재하는 list를 이동하는데, 시작점인 first를 계속해서 갱신해주면서 

찾으려는 목표 숫자인 x를 찾아주고, 찾는 즉시 list에서 제거해줬다.

 

조금 어렵게 생각한 듯 하다 .. 다른 분 풀이를 보니까 Deque를 이용해서 문제를 풀었는데,

이분탐색처럼 배열 내 Deque 내 중간값 idx와 구하려는 x의 idx를 구한 다음

중간값 idx < x idx 일 경우 idx+1~N쪽으로 접근해 last 숫자들을 first로 옮겨주고(3번연산)

중간값 idx >= x idx 일 경우 0~idx-1 으로 접근해 first 숫자들을 last로 옮겨주고(2번연산)

맨 앞에 있는 값을 pop해서 문제를 해결하셨더라고요.

저보다 더 쉽게 푸신 것 같아서 공부가 됐습니다 👍🏻

 

 

package 백준renew;

import java.io.*;
import java.util.*;

public class 실버3_1021_회전하는큐 {
	static int N, M, first, ans;
	static int arr[];
	static List<Integer> list = new ArrayList<>();
	static int visited[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		first = 0;
		ans = 0;
		
		arr = new int[M];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			int tmp = Integer.parseInt(st.nextToken());
			arr[i] = tmp;
		}
		
		for(int i=1; i<=N; i++) {
			list.add(i);
		}
		
		for(int i=0; i<M; i++) {
			visited = new int[list.size()];
			Move(arr[i]);
		}
		
		sb.append(ans);
		bw.write(sb.toString());
		bw.close();
		
	}
	static void Move(int x) {
		Queue<Integer> q = new LinkedList<>();
		q.add(first);
		visited[first] = 1;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			int newX = 0;
			int num = list.size();
			
			if(list.get(now) == x) {
				ans += (visited[now]-1);
				list.remove(now);
				if(list.size() <= now) {
					first = (now + num+1)%num;
				}else {
					first = now;
				}
				break;
			}else {
				for(int i=0; i<2; i++) {
					if(i==0) {
						newX = (now + num-1)%num;
					}else {
						newX = (now + num+1)%num;
					}
					
					if(visited[newX] != 0) {
						continue;
					}
					
					q.offer(newX);
					visited[newX] = visited[now] + 1;
				}
			}
		}
		
	}
}