[백준] 2164번 : 카드2 - JAVA [자바]

 
www.acmicpc.net/problem/2164

2164번: 카드2

 

 

 

---

• 문제

 

 

 

 

큐에 대한 원리만 알고 있어도 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

 

이 번 문제같은 경우 자료구조를 한 번쯤 접해봤거나 큐에 대한 개념이 있다면 쉽게 풀 수 있는 문제다.

잠깐 큐에 대해 설명하자면 큐 자료구조의 경우 '선입선출' 자료구조로 말 그대로 먼저 들어간 요소가 먼저 나오는 방식이다. 쉽게 생각해서 놀이기구를 타기위해 줄서있는 모습을 생각하면 된다.

 

큐에 대한 자세한 내용과 구현은 아래 글을 참고하시길 바란다.

자바 [JAVA] - 배열을 이용한 Queue (큐) 구현하기

 

 

만약 연결리스트로 구현 된 것을 보고싶다면 아래 링크를 참고하면 된다.

자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기

 

 

 

 

문제를 풀이하는 방법은 매우 쉽다. 맨 앞의 수를 삭제하고(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 문제도 있으니 한 번 풀어보시는 것을 추천한다.