[백준] 1021-회전하는 큐-Java
in Algorithm on Algorithm
[백준] 1021-회전하는 큐-Java
❓문제
- 회전하는 양방향 순환 큐가 있다.
- 해당하는 큐에서는 다음과 같은 3가지 연산을 수행할 수 있다.
- 첫 번째 원소를 뽑아낸다.
- ex) {1,2,3,4} -> {2,3,4}
- 왼쪽으로 한 칸 이동시킨다.
- ex) {1,2,3,4} -> {2,3,4,1}
- 오른쪽으로 한 칸 이동시킨다.
- ex) {1,2,3,4} -> {4,1,2,3}
- 첫 번째 원소를 뽑아낸다.
첫째줄 입력값으로는 N, 뽑아내려는 수의 개수 M이 주어진다.
- 큐는 1~N까지의 수로 구성되어 있다. 둘째줄 입력값으로는 뽑아내야하는 원소가 M개만큼 순서대로 주어진다.
뽑아내려는 원소를 순서대로 뽑아내는데 드는 2번,3번 연산의 최솟값을 출력하라.
🖊️풀이법
이번 문제는 회전하는 큐지만, 양방향으로 원소를 넣고 빼야하기때문에 덱의 성질을 가진다.
해당 문제에서는 뽑아내야하는 원소의 인덱스를 파악하기 위해서 LinkedList를 사용하였다.
문제를 풀기전 간단하게 수도코드를 작성해보았다.
- 1 ~ N까지의 원소를 담는다.
- M을 입력받는다.
- M번만큼 반복문을 순회한다.
- 원소의 idx가 왼쪽으로 가는 횟수와 오른쪽으로 가는 횟수를 비교한다.
- 둘중 더 작은 쪽으로 인덱스의 위치를 한칸씩 옮긴다.
- 인덱스의 위치가 옮겨질때마다 count값을 1씩 증가시킨다.
- 인덱스가 0번째 위치에 오면 해당 원소를 빼낸다.
- 반복문이 종료되면 count값을 출력한다.
정답 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st= new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
LinkedList<Integer> deque = new LinkedList<>();
for(int i = 1; i <= N; i++){ //덱에 원소를 1~N까지 넣어준다.
deque.offer(i);
}
int count = 0; //정답을 닮을 count를 초기화
st = new StringTokenizer(br.readLine());
while(M-- > 0){ //M번만큼 반복문 수행
int key = Integer.parseInt(st.nextToken()); //빼내야 하는 원소를 key값에 할당
int idx = deque.indexOf(key); //덱에서 Key의 인덱스를 확인
if(idx <= deque.size() - idx){ //만약 원소가 왼쪽가 가깝다면
if(deque.get(0) == key){ //덱의 원소가 맨앞의 경우
deque.poll(); //바로빼낸다.
} else { //아닌경우
for (int i = 0; i < idx; i++) { //인덱스만큼 반복문을 실행
deque.offer(deque.poll()); //맨앞의 원소를 맨 뒤로 옮긴다.
count++; //카운트 증가
}
deque.poll(); //key값이 맨앞으로 왔을 때 빼낸다.
}
} else { //만약 원소가 오른쪽에 가깝다면
for (int i = 0; i < deque.size() - idx; i++) { //덱크기 - 인덱스만큼 반복문 실행
deque.add(0, deque.get(deque.size()-1)); //덱의 맨뒤의 값을 맨앞에 넣고
deque.remove(deque.size() - 1); //덱의 맨뒤의 원소를 삭제한다.
count++; //카운트 증가
}
deque.poll(); //key값이 맨앞으로 왔을 때 빼낸다.
}
}
System.out.println(count); //반복문 종료 후 count값 출력
}
}
정리
수도코드를 간단하게 작성하면, 쉽게 코드를 구현할 수 있다.
매번 수도코드를 작성하진 않지만.. 항상 먼저 구현 이전에 수도코드를 작성하는 습관을 가지자!