[백준] 회전하는 큐 1021번
나의 풀이
public class RotatingQueue {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int M = Integer.parseInt(s[1]);
int count = 0;
LinkedList<Integer> deque = new LinkedList<>();
for(int i = 1; i < N + 1; i++) {
deque.add(i);
}
String[] nums = br.readLine().split(" ");
for(int i = 0; i < M; i++) {
int index = 0;
int halfIndex = 0;
int pickNum = Integer.parseInt(nums[i]);
if(deque.peekFirst() == pickNum) {
deque.pollFirst();
continue;
}
index = deque.indexOf(pickNum);
if(deque.size() % 2 == 0) {
halfIndex = deque.size() / 2 - 1;
} else {
halfIndex = deque.size() / 2;
}
if(index > halfIndex) {
while(deque.peekFirst() != pickNum) {
count++;
deque.addFirst(deque.pollLast());
}
} else {
while(deque.peekFirst() != pickNum) {
count++;
deque.addLast(deque.pollFirst());
}
}
deque.pollFirst();
}
System.out.println(count);
}
}
- Queue 를 사용할 경우 get 이나 indexOf 와 같이 큐 안에서 원소를 찾는 메소드가 없기 때문에 LinkedList 나 List 를 사용하는 것이 좋다.
- 만약 뽑아야할 수가 큐의 첫번째 요소와 같다면 큐를 좌, 우로 움직일 필요가 없으므로 count를 증가시키지 않고 바로 빼주고 continue 를 통해 다음 연산을 진행한다.
- 같지 않다면 움직여 줘야 한다.
- 우선 뽑아야할 숫자가 현재 큐에서 몇번째 인덱스에 있는지 알아야 한다. 그렇기 때문에 indexOf 메소드를 사용해서 인덱스를 추출해준다.
- 인덱스가 큐의 중간보다 크다면 오른쪽으로, 작다면 왼쪽으로, 같다면 좌우 상관없이 움직여 줘야 한다.
- 하지만 큐가 짝수이거나 홀수일 때를 주의해야 한다. 컴퓨터는 인덱스를 0부터 세기 때문에 짝수일 경우는 큐의 사이즈를 2로 나눌 경우 중간 값을 넘어가기 때문이다. 따라서 큐의 사이즈가 짝수라면 2로 나눈 값에서 -1을 해주고, 홀수라면 그냥 2로 나눠준 값을 중간 인덱스 값으로 활용한다.
- 만약 뽑아야할 숫자의 인덱스가(index) 중간 인덱스(halfIndex) 보다 크다면, 큐의 첫번째 원소가 뽑아야 할 숫자(pickNum)과 같아질 때까지 오른쪽으로 이동시켜주고, 카운트를 1씩 증가시킨다.
- 반대로 중간 인덱스보다 작거나 같으면 똑같이 pickNum과 같아질 때까지 왼쪽으로 이동시켜주고, 카운트를 1씩 증가시킨다.
- 이동이 모두 끝난 후에는 큐에서 해당 원소를 제거해준다.