백준 - 회전하는 큐[java]
출처: https://www.acmicpc.net/problem/1021
문제설명
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
문제의 설명은 다음과 같다.
쉽게 말해서,
이렇게 된 원형 큐가 있는데 index 0 에서만 숫자를 꺼낼 수 있고,
왼쪽 또는 오른쪽으로 돌려서 입력된 숫자를 하나씩 찾는 문제이다.
그때 최소 회전수를 리턴하면 된다.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int len = Integer.parseInt(st.nextToken());
int total = Integer.parseInt(st.nextToken());
LinkedList<Integer> ll = new LinkedList<>();
LinkedList<Integer> ll2 = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= len; i++) {
ll.add(i);
ll2.add(i);
}
int count = 0;
while (total-- > 0) {
int clockwiseCount = 0;
int counterClockwiseCount = 0;
int cur = Integer.parseInt(st.nextToken());
while (true) {
int first = ll.pollFirst();
if (first != cur) {
clockwiseCount++;
ll.addLast(first);
} else
break;
}
while (true) {
int first = ll2.getFirst();
if (first == cur) {
ll2.pollFirst();
break;
}
int last = ll2.pollLast();
counterClockwiseCount++;
ll2.addFirst(last);
}
count += Math.min(clockwiseCount, counterClockwiseCount);
}
System.out.println(count);
br.close();
}
}
앞과 뒤에서 모두 숫자를 꺼내기 위해 LinkedList 자료구조를 사용했다.
시계방향, 시계반대방향으로 회전시킬 두개의 LinkedList를 만들었다.
각 숫자를 찾을때 마다 시계 반대방향, 시계 방향 중 더 적은 횟수를 회전한 쪽을 계속해서 count에 더한다.
Author And Source
이 문제에 관하여(백준 - 회전하는 큐[java]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@davidko/백준-회전하는-큐java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)