Queue10

• 

  [JAVA] Queue 인터페이스 구현하기 (3) ArrayDeque Queue라는 인터페이스를 구현하는 방식 중 ArrayDeque에 대해서 알아본다. add - offer이 완전히 동일한 것을 제외하면 나머지는 queue 추상메서드의 의도대로 구현되었다. ArrayDeque ArrayDeque은 내부적으로 다음의 변수를 사용한다. 이 변수들은 transient를 사용해서 직렬화되지 않는다. Object[] elements deque의 요소가 저장되는 배열. 항상 2의 거듭제곱이 배열의 길이가 된다. deque요소를 보유하지 않는 모든 배열 셀은 항상 null이다. int head deque의 head 요소의 "인덱스". deque가 비어있는 경우 tail과 같은 임의의 숫자가 저장된다. int tail deque의 다음요소가 추가될 "인덱스". private int M.. 기록/JAVA 2023. 7. 11.

• 

  [JAVA] Queue 인터페이스 구현하기 (2) LinkedList Queue라는 인터페이스를 구현하는 방식 중 LinkedList에 대해서 알아본다. LinkedList LinkedList는 내부적으로 다음의 변수를 사용한다. 이 변수들은 transient를 사용해서 직렬화되지 않는다. int size 크기 Node first 첫번째 노드를 가리킨다. Node last 마지막 노드를 가리킨다. modCount는 LinkedList가 상속받은 AbstractSequentialList 내부적으로 쓰이는 변수다. 객체의 구조적 변경 횟수를 추적하기 위해 사용된다. Node LinkedList에서 사용하는 Node 클래스다. 한 노드에는 아이템과 이전 노드 주소, 다음 노드 주소를 저장한다. private static class Node { E item; Node next; .. 기록/JAVA 2023. 7. 11.

• 

  [JAVA] Queue 인터페이스 구현하기 (1) Queue Queue라는 인터페이스를 구현하는 방식은 일반적으로 ArrayDeque, LinkedList 두 가지가 있다. 이 두 가지 클래스가 Queue의 추상메서드를 어떤 식으로 수행하는지 비교해보고자 한다. (java 1.8 기준) 그 이전에, 큐가 어떤 것인지부터 짚어본다. Queue란? 큐는 데이터를 일시적으로 저장하고 처리하는 자료구조다. 데이터를 먼저 입력한 순서대로 저장하고, 먼저 입력된 데이터가 먼저 처리되는 FIFO(First-In-First-Out)원칙을 따른다. 은행 창구, 버스정류장 등 일반적인 일상생활에서의 대기줄을 생각하면 쉽다. Queue 추상 메서드 목록 Queue 인터페이스에는 다음과 같은 추상 메서드가 있다. 이 메서드를 잘 기억해서, ArrayDeque이나 LinkedList에서.. 기록/JAVA 2023. 7. 10.

• 

  [BOJ] 2161 카드1 - JAVA 1. 문제 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 .. 코딩테스트/BOJ 2023. 2. 10.

• 

  [BOJ] 3190 뱀 - JAVA 1. 문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저.. 코딩테스트/BOJ 2022. 4. 7.

• 

  [BOJ] 1021 회전하는 큐 - JAVA 1. 문제 2. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class BOJ_1021_회전하는큐 { public static void main(String[] args) throws IOException { //입력 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokeni.. 코딩테스트/BOJ 2022. 2. 7.

• 

  [BOJ] 1966 프린터큐 - JAVA 1. 문제 2. 풀이 생각한 방식은 아래와 같다. 0. idx : 찾으려고 하는 요소의 인덱스. 문서들을 이동할 때마다 매번 바꿔줘야 한다. order : 지금까지 몇 장 프린트했는지. 맨 앞 문서를 프린트할 때마다 +1한다. 1. 정렬한 nums를 뒤에서부터 돌아가면서 체크한다. (Arrays.sort(nums,Collections.reverseOrder())를 사용하면 앞에서부터 체크해도 된다. 그냥 타입 바꾸기 싫어서 이렇게 했다..) 2. 체크할 때, 해당 nums[i] (이하 num이라 함) 이 queue.peek()과 같아질 때까지 맨 앞 요소를 뒤로 보낸다. 이 때, idx가 0이면 다음 idx는 큐의 사이즈-1가 된다. 0이 아니면 그냥 -1. 3. num==queue.peek()이 되면 .. 코딩테스트/BOJ 2022. 2. 7.

• 

  [BOJ] 11866 요세푸스 문제 0 - JAVA 1. 문제 2. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ_11866_요세푸스문제0 { public static void main(String[] args) throws IOException { StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine()); int N .. 코딩테스트/BOJ 2022. 2. 6.

• 

  [BOJ] 2164 카드2 - JAVA 1. 문제 2. 풀이 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BOJ_2164_카드2 { public static void main(String[] args) { int N = new Scanner(System.in).nextInt(); Queue queue = new LinkedList(); for(int i=1;i1){ queue.poll(); queue.add(queue.poll()); } System.out.println(queue.poll()); } } 입력도 간단하고 출력도 간단한 문제였다. queue.size가 1일때 끝내기만 하면 되니까 그 전까지 반복문을 돌려줬다. .. 코딩테스트/BOJ 2022. 2. 6.

• 

  [BOJ] 18258 큐2 - JAVA 1. 문제 2. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.StringTokenizer; public class BOJ_18258_큐2 { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(in.readLine()); LinkedList queue = new Link.. 코딩테스트/BOJ 2022. 2. 6.