[백준] 백준 2161 카드1 자바 – JAVA

백준 2161 카드1 자바 문제 해결과정입니다.

백준 2161 카드1

백준 2161 카드1

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.

예제 입력	예제 출력
7	1 3 5 7 4 2 6

해결 방식

큐 하나로 해결하기

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Queue<Integer> queue = new LinkedList<>();
		for(int i = 1; i <= n; i++) {
			queue.offer(i);
		}
		
		while(queue.size() > 1) {
			System.out.printf("%d " , queue.poll());
			queue.offer(queue.poll());
		}
		System.out.println(queue.peek());
		
	}
}

큐를 선언하여 문제를 해결했다. scanner을 통해 사용자에게 수를 입력받아 n으로 저장한다. for문을 통해 1부터 n까지의 값을 큐에 넣어준다. 이때 큐는 FIFO구조 이므로 offer 메소드를 통해 수를 큐의 rear에 저장되도록 한다. 큐에서 버릴 모든 카드들을 순서대로 출력해야 하므로 while문을 통해 큐의 요소가 없어질 때까지 반복하도록 하여 남는 요소가 없도록 한다. 이후에 format형식의 print문을 통해 poll 메소드로 한번 추출되고 버려지는 큐의 값을 출력하도록 하고, offer 메소드를 통해 poll 될 값을 다시 큐의 뒤로 넣어준다. while문이 다 돌고 나면 큐에는 요소 하나가 남게 되는데 peek를 통해 마지막 요소도 출력해준다.

위의 방식도 있고 큐를 두 개를 사용하여 해결하는 방식이 있다.

큐 두 개로 해결하기

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Queue<Integer> queue = new LinkedList<>();
		Queue<Integer> queue2 = new LinkedList<>();
		int n = sc.nextInt();
		for(int i = 1; i <= n; i++) {
			queue.offer(i);
		}
		while(queue.size() > 1) {
			queue2.offer(queue.poll());
			queue.offer(queue.poll());
		}
		queue2.offer(queue.poll());
        
		while(queue2.size() > 1) {
			System.out.print(queue2.poll() + " ");
		}
		System.out.println(queue2.poll());

	}
}

위 코드는 두 개의 큐를 사용하는데 하나는 처음에 값이 들어가 생성될 큐1이고, 두 번째 큐는 출력할 값들을 넣어줄 큐2이다. 첫번째 코드와 똑같이 입력받을 값을 선언하고 큐를 선언한다. 이후에 for문을 통해 큐1을 설정해준다. while문을 통해 큐1의 모든 값들이 없어질 때까지 반복시키며 첫 줄에 큐2에 큐1에서 버려진 값을 넣어준다. 이후에 2번째 줄에는 큐1의 front에 있는 것을 큐1의 rear에 넣어주는 코드를 작성해주었다. 마지막에 남은 요소를 처리하기 위해 queue2.offer(queue.poll());을 써주었다. 이후에 큐2에는 버려진 순서의 모든 요소들이 들어가 있어서 while문으로 모든 요소들을 출력해준다. 마지막에 요소가 하나 남아있어 앞의 코드와 같이 처리해주었다.

최신글

• 
  [프로그래머스] 잘라서 배열로 저장하기 – 자바
• 
  [프로그래머스] 붕대 감기 – 자바
• 
  [프로그래머스] 달리기 경주 – 자바