[java] 문제 013 (백준 2164)

문제

카드2

 

교재 풀이

import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
public class P2164_카드 {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 Queue<Integer> myQueue = new LinkedList<>();
 int N = sc.nextInt();
 for (int i = 1; i <= N; i++) { // 카드를 큐에 저장하기
 myQueue.add(i);
 }
 while (myQueue.size() > 1) { // 카드가 1장 남을 때까지
 myQueue.poll(); // 맨 위의 카드를 버림
 myQueue.add(myQueue.poll()); // 맨 위의 카드를 가장 아래 카드 밑으로 이동
 }
 System.out.println(myQueue.poll()); // 마지막으로 남은 카드 출력
 }
}

 

설명

myQueue.size() > 1

=> 큐에 size()라는 메소드도 있구나. 다음엔 이걸 써야 겠다

 

24.6.6) 내 풀이, 맞음

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws IOException {
	//	N장의 카드가 있다. 
	//	    각각의 카드는 1부터 N까지의 번호가 붙어 있으며
	//	    1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
	//    카드가 한 장 남을 때까지 반복하게 된다.
	//        우선, 제일 위에 있는 카드를 바닥에 버린다.
	//        그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
    //    N=4인 경우를 생각해 보자.
    //        카드는 제일 위에서부터 1234 의 순서로 놓여있다.
    //        1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다.
    //        3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다.
    //        마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
    //    N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램
    //        첫째 줄에 정수 N(1 ≤ N ≤ 500,000)
    //    접근법
    //        딱 보자마자 큐인 게 떠오름
    //        핵심 로직이 다음인데
    //            front 카드 poll해주고
    //            다시 front 카드 poll하고 rear에 add해주고 
    //            이거를 언제까지 반복? 한 장 남을 때까지. 즉 큐의 원소 개수가 하나일 때까지 
    //        그리고 남은 원소 하나를 출력하면 끝 아님?
    //    슈도 코드 
    //        먼저 n을 입력받음 
    //        큐를 선언함
    //        큐에 순서대로 1부터 n까지 add해줌
    //        
    //        for or while로 원소가 하나 남을 때까지
    //            front 카드 poll해주고
    //            다시 front 카드 poll하고 rear에 add해주고 
    //        남은 원소 출력하고 끝 
        
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        
        Queue<Integer> que=new LinkedList<>();
        for(int i=1;i<=n;i++){
            que.add(i);
        }
        
        //핵심 로직 
        for(int i=0;i<n-1;i++){
            que.poll();
            que.add(que.poll());
        }
        
        System.out.println(que.poll());
	}
}