백준 2162번 카드2(JAVA)

2164번: 카드2

 

풀이코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");
        
        int N = Integer.parseInt(st.nextToken());
        Queue<Integer> cards = new LinkedList<>();
        
        for (int i = 1; i <= N; i++) {
           cards.offer(i);
        }
        
        for (int i = 0; ; i++) {            
            if (cards.size() == 1) {
                break;
            }

            if (i % 2 == 0) { 	// 카드 버리기
                cards.poll();
            } else { // 제일 밑에 깔아주기
                cards.offer(cards.poll());
            }
        }
        
        System.out.print(cards.peek());

        cards.clear();
    }
}

 

풀이과정

카드를 버리든, 카드를 맨 뒤로 넣든 맨 앞 카드를 빼는 점에서 큐를 이용하였다.

cards.offer(i);

1 ~ N 까지 카드를 큐에 넣어준다.

 

cards.poll();

poll() 함수는 큐 가장 앞에 있는 숫자를 꺼낸다. 맨 앞 카드 버리기, 맨 뒤로 카드 넣기 모두 맨 앞 카드를 꺼낸다는 공통점이 있어 해당 함수를 활용하였다.

 

cards.offer(cards.poll());

poll() 함수로 꺼낸 숫자를 다시 큐에 넣어준다. 큐는 선입선출 구조이므로 방금 넣은 숫자는 큐의 맨 뒤로 가게 된다.

 

int number = cards.poll(); 
cards.offer(number);

이를 변수를 사용하여 풀어쓰면 위와 같이 나타낼 수 있다. 

예를 들어 cards에 {2, 4, 3}이 있다고 가정하면,

int number = cards.poll() 실행 후 cards는 {4, 3} 이고, number은 2이고, cards.offer(number) 실행 후 cards는 {4, 3, 2} 이다.

 

풀면서 고려하지 못한 점은 N이 1인 케이스이다.

for (int i = 0; ; i++) {
    if (i % 2 == 0) { 	// 카드 버리기
        cards.poll();
    } else { // 제일 밑에 깔아주기
        cards.offer(cards.poll());
    }            

    if (cards.size() == 1) {
        break;
    }
}

처음에는 if (cards.size() == 1) 를 for문 마지막에 작성했었는데, 이러면  1개 밖에 없는 카드를 버리고 cards.size()는 0이 되어 무한 루프에 빠지고 만다 ..

따라서 큐의 사이즈를 체크하는 조건문을 반복문 가장 위에 작성하였다.

N이 1이면 큐의 사이즈가 이미 1이기 때문에 카드를 버리거나 제일 밑으로 보내주는 행위없이 반복문을 종료하게 된다.