[BaekJoon] 2164번 카드2 문제 풀이 (Success)

2164번: 카드2

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        Queue<Integer> queue = new LinkedList<>();
 
        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }
 
        while (queue.size() > 1) {
            queue.remove();
            queue.add(queue.poll());
        }
 
        bw.write(queue.peek().toString());
 
        bw.flush();
        bw.close();
 
    }
 
}
 

🤔 해설

1. for (int i = 1; i <= N; i++) { ... }

    - 1~N까지 queue에 입력

 

2. while (queue.size() > 1) { ... }

    - 최종으로 값이 1개 남을 때까지 반복문 진행

    - queue.remove();

        - 선입선출에 의해 첫번째 입력값 제거

    - queue.add(queue.poll());

        - 선입선출에 의해 첫번째 입력값 제거 후 마지막에 입력

 

* remove(): 큐가 비어있을 때 호출 시, NoSuchElementException 발생

  poll(): 큐가 비어있을 때 호출 시, 예외를 발생시키지 않고 null 반환

 

3. bw.write(queue.peek().toString());

    - 최종으로 남은 값 출력

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        int[] iQueue = new int[N * 2];
 
        for (int i = 1; i <= N; i++) {
            iQueue[i] = i;
        }
 
        int idx_first = 1;
        int idx_last = N;
        while (N-- > 1) {
            idx_first++;
            idx_last++;
            iQueue[idx_last] = iQueue[idx_first];
            idx_first++;
        }
 
        bw.write(iQueue[idx_first] + "");
 
        bw.flush();
        bw.close();
 
    }
}
 

1. int[] iQueue = new int[N * 2];

    - 배열: 1부터 시작

    - 배열 삭제를 구현하지 않고, 마지막 요소의 뒤이어 추가 예정

        - 최종 1개는 출력만 하면되므로 2N-1이 될 수 있지만, 인덱스를 1부터 시작하므로 필요한 배열 공간은 2N

 

2. while (N-- > 1) { ... }

    - idx_first++, idx_last++

        - 2번째 값을 맨 마지막의 다음 칸에 입력해야하므로 1씩 증가

    - idx_first++

        - 삭제 후 맨 처음값을 맨 뒤로 옮겼으므로, 그 다음 값은 단순 삭제 대상이므로 idx_first 1 증가

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

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