-
[백준/BOJ] 1021번 : 회전하는 큐 (JAVA / 자바)백준 2022. 2. 21. 21:28
안녕하세요~ 코딩하는 코알못 코메인입니다.
https://www.acmicpc.net/problem/1021
- 문제 -
난이도 실버 4 문제이다.
자바에서 입력방식은 scanner와 bufferedreader가 있다.
자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.
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); } }
-결과-
아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.
'백준' 카테고리의 다른 글
[백준/BOJ] 1392번 : 노래 악보 (JAVA / 자바) (0) 2022.02.22 [백준/BOJ] 1003번 : 피보나치 함수 (JAVA / 자바) (0) 2022.02.22 [백준/BOJ] 1002번 : 터렛 (JAVA / 자바) (0) 2022.02.21 [백준/BOJ] 1181번 : 단어 정렬 (JAVA / 자바) (2) 2022.02.20 [백준/BOJ] 1158번 : 요세푸스 문제 (JAVA / 자바) (0) 2022.02.20