[백준] 2164번 : 카드2 - JAVA [자바]
-
문제
큐에 대한 원리만 알고 있어도 쉽게 풀 수 있는 문제다.
- 알고리즘 [접근 방법]
이 번 문제같은 경우 자료구조를 한 번쯤 접해봤거나 큐에 대한 개념이 있다면 쉽게 풀 수 있는 문제다.
잠깐 큐에 대해 설명하자면 큐 자료구조의 경우 '선입선출' 자료구조로 말 그대로 먼저 들어간 요소가 먼저 나오는 방식이다. 쉽게 생각해서 놀이기구를 타기위해 줄서있는 모습을 생각하면 된다.
큐에 대한 자세한 내용과 구현은 아래 글을 참고하시길 바란다.
만약 연결리스트로 구현 된 것을 보고싶다면 아래 링크를 참고하면 된다.
문제를 풀이하는 방법은 매우 쉽다. 맨 앞의 수를 삭제하고(poll), 그 다음 앞의 수를 삭제한 뒤(poll) 삭제한 수를 맨 뒤에 삽입(offer)한다. 이런 과정을 수가 1개 남을 때 까지 무한 반복 하는 것이다. 총 3개의 과정이 있는 것이다.
즉, 두 가지 메소드 poll, offer만 이해하면 쉽게 풀이할 수 있다. 좀 더 그림으로 쉽게 보자면 이렇다.
이를 구현하는 여러가지가 있지만 대표적으로 자바에서 지원하는 큐를 써서 풀이할 수도 있고, 배열로도 풀이 할 수 있다.
Queue 라이브러리를 이용하여 간단하게 짜면 이렇다.
[방법 1]
while(q.size() > 1) { // 원소가 한 개만 남을 때 까지
q.poll();
int temp = q.poll();
q.offer(temp);
}
print(q.poll()); // 마지막으로 남은 원소 출력
또는 다른 방법으로는 직접 구현하는 것이다. 굳이 삭제해줄 필요 없이 다음과 같이 첫 번째 요소와 마지막 요소의 위치(Index)를 가리키는 변수를 두고 쓰면 된다. 말로하긴 어려우니 코드로 보면 이렇다.
[방법 2]
// 원소는 인덱스 1부터 N까지 채웠다고 가정 (index 0은 쓰지 않음)
prev_index = 1;
last_index = N;
for(int i = N; i > 1; i--) {
prev_index++; // 삭제할 필요 없이 prev가 가리키는 첫 번째 원소를 다음 원소로 변경
q[last_index + 1] = q[prev_index]; // 마지막 원소 다음공간에 현재 첫 번째 원소 데이터를 삽입
// 각각 변수가 가리키는 인덱스를 1 씩 증가
last_index++;
prev_index++;
}
print(q[prev_index]); // 마지막으로 남은 원소 출력
- 3가지 방법을 사용하여 풀이한다.
라이브러리를 이용한 방법과 앞서 말한 배열을 이용한 방법 두 가지를 비교해 볼 것이다. 또한 각각의 입력에 따른 성능도 비교해보고자 한다. 즉 아래와 같이 4가지 방식을 보여줄 것이다.
1. Scanner + 방법 1
2. Scanner + 방법 2
3. BufferedReader + 방법 1
4. BufferedReader + 방법 2
- 풀이
- 방법 1 : [Scanner + 방법 1]
import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Queue<Integer> q = new LinkedList<>();
int N = in.nextInt();
for(int i = 1; i <= N; i++) {
q.offer(i);
}
while(q.size() > 1) {
q.poll(); // 맨 앞의 원소 버림
q.offer(q.poll()); // 맨 앞의 원소를 버림과 동시에 버려진 원소를 맨 뒤에 삽입
}
System.out.println(q.poll()); // 마지막으로 남은 원소 출력
}
}
LinkedList 라이브러리를 이용한 가장 기본적인 방법이다.
Queue<Integer> q = new LinkedList<>(); 대신 LinkedList<Integer> q = new LinkedList<>(); 로 선언해주어도 무방하다.
- 방법 2 : [Scanner + 방법 2]
배열로 풀이하는 방법이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
/**
* 한 턴에 1개 씩 삭제되고 뒤에 1개가 추가 되므로
* 2 * N - 1 의 공간이 필요하다.
* 다만 index는 1부터 시작할 것이기 때문에
* 2 * N 공간으로 생성한다.
*/
int[] q = new int[2 * N];
for(int i = 1; i <= N; i++) {
q[i] = i;
}
int prev_index = 1;
int last_index = N;
while(N-- > 1) {
prev_index++;
q[last_index + 1] = q[prev_index];
last_index++;
prev_index++;
}
System.out.println(q[prev_index]);
}
}
큐의 원리만 잘 이해한다면 아마 크게 어렵지 않을 것이다.
- 방법 3 : [BufferedReader + 방법 1]
알고리즘의 방법 1에서 Scanner 대신 BufferedReader로 풀이한 방법이다.
import java.util.Queue;
import java.util.LinkedList;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> q = new LinkedList<>();
int N = Integer.parseInt(br.readLine());
for(int i = 1; i <= N; i++) {
q.offer(i);
}
while(q.size() > 1) {
q.poll(); // 맨 앞의 원소 버림
q.offer(q.poll()); // 맨 앞의 원소를 버림과 동시에 버려진 원소를 맨 뒤에 삽입
}
System.out.println(q.poll()); // 마지막으로 남은 원소 출력
}
}
크게 어려울 것은 없을 것이다. 각 필요 기능별로 메소드를 구현해놓았으니 참고하시길 바란다.
- 방법 4 : [BufferedReader + 방법 2]
마찬가지로 알고리즘의 방법 2에서 Scanner 대신 BufferedReader로 풀이한 방법이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
/**
* 한 턴에 1개 씩 삭제되고 뒤에 1개가 추가 되므로
* 2 * N - 1 의 공간이 필요하다.
* 다만 index는 1부터 시작할 것이기 때문에
* 2 * N 공간으로 생성한다.
*/
int[] q = new int[2 * N];
for(int i = 1; i <= N; i++) {
q[i] = i;
}
int prev_index = 1;
int last_index = N;
while(N-- > 1) {
prev_index++;
q[last_index + 1] = q[prev_index];
last_index++;
prev_index++;
}
System.out.println(q[prev_index]);
}
}
- 성능
채점 번호 : 20597227 - 방법 4 : BufferedReader + 방법 2
채점 번호 : 20597227 - 방법 3 : BufferedReader + 방법 1
채점 번호 : 20597227 - 방법 2 : Scanner + 방법 2
채점 번호 : 20597227 - 방법 1 : Scanner + 방법 1
입력과의 차이도 차이이지만, 라이브러리를 사용하는 것과 사용하지 않고 직접 쓰는 방법 간에도 차이가 나는 것을 볼 수 있다.
- 정리
워낙 쉬웠던 문제라 크게 어렵지 않게 풀 수 있었을 것이다.
또한 비슷한 문제로 카드 1 문제도 있으니 한 번 풀어보시는 것을 추천한다.
'JAVA - 백준 [BAEK JOON] > 큐, 덱' 카테고리의 다른 글
[백준] 1021번 : 회전하는 큐 - JAVA [자바] (0) | 2021.02.27 |
---|---|
[백준] 10866번 : 덱 - JAVA [자바] (8) | 2021.02.19 |
[백준] 1966번 : 프린터 큐 - JAVA [자바] (10) | 2021.02.03 |
[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바] (10) | 2021.01.23 |
[백준] 18258번 : 큐 2 - JAVA [자바] (5) | 2020.12.13 |