[백준/BOJ] 1021번 : 회전하는 큐 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

---

- 문제 -

 

난이도 실버 4 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

처음엔 제목을 보고 큐를 생각했고, 문제를 보고 큐하고 연관된 덱을 생각했다. 하지만 원하는 값의 위치를 알아야하는데 인덱스 값들을 건들지 않고, 덱에서 위치를 알아내는 방법을 아무리 구글링을 해도 나오지가 않았다.(아시는 분 있다면 댓글로 부탁드립니다...) 그래서 저장된 값들을 앞에서 뒤로 뒤에서 앞으로 자유롭게 보낼 수 있으면 서 원하는 값의 위치도 알 수있는 내장 함수를 가진 Linkedlist를 사용하기로 했다.

 

문제에대한 풀이를 보자.

입력값 N과 M이 주어진다. list에 1~N까지 모든 값을 순서대로 집어넣는다. 

M의 개수만큼 제외시킬 값을 입력받는다.

입력받은 값이 맨 앞에 있다면, 그대로 제외 시키지만, 맨 앞에 있지 않는다면 맨앞에 위치할때까지 옮겨줄 반복문을 만든다. 하지만 옮기는 횟수를 최소로해야하기 때문에 제외시킬 값의 인덱스 값을 가져와 중심기준에서 앞에 있는지 뒤에있는지 판단한다.

앞에 있다면 맨 앞 값들을 제외시킬 값이 올때까지 하나씩 맨 뒤로 이동시켜준다.

뒤에 있다면 맨 뒤 값들을 제외시킬 값이 올때까지 하나씩 맨 앞으로 이동시켜준다.

옮겨질때마다 반복되는 횟수를 구한다.

반복문 이후 맨 앞에 제외시킬 값이 위치한다면 제외 시켜준다. 이 것을 M번만큼 반복해준다.

 

코드로 보자.

---

-풀이-

 

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 N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		LinkedList<Integer> Deq = new LinkedList<Integer>();
		
		//LinkesList에 1부터 N값까지 순서대로 저장한다.
		for(int i = 1; i <= N; i++) {
			Deq.add(i);
		}
		
		//이동 룃수를 저장 할 변수
		int count = 0;
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			int num = Integer.parseInt(st.nextToken());
			
			//num값이 맨 앞에 올때까지 반복한다.
			while(Deq.getFirst() != num) {
				if(Deq.indexOf(num) <= (Deq.size() / 2)) {
					Deq.addLast(Deq.getFirst());
					Deq.removeFirst();
				}else {
					Deq.addFirst(Deq.getLast());
					Deq.removeLast();
				}
				count++;
			}
			//num값이 맨 앞에 위치하면 그 값을 제외시킨다.
			if(Deq.getFirst() == num) {
				Deq.removeFirst();
			}
		}
		System.out.println(count);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.