[Java] 백준(실버-4) 2164번 - 카드2

문제 풀이

---

이번 문제는 큐의 선입선출(FIFO) 기능을 알고 활용할 줄 알면 쉽게 풀 수 있다.

아이디어 도출

• N을 입력받으면 1부터 N까지의 수를 Queue에 삽입한다.
• 큐의 삽입된 값이 1개가 될 때까지 아래 작업을 수행한다.
  • front(맨앞의 수)를 하나 삭제한다.
  • front(새로운 맨앞의 수)를 추출하여 새로 삽입한다.
• 위 과정을 반복하며 큐의 값이 1개가 된다면 큐의 front값을 출력한다.

아이디어는 굉장히 단순하다. 중요한 부분은 front(맨 앞의 수)를 추출한 후 변경된 front값을 맨 뒤로 보내는 것이다.
바로 코드를 작성해보자.

int N = Integer.parseInt(br.readLine());
Queue<Integer> qu = new LinkedList<>();

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

먼저 N을 입력받고 1부터 N까지의 수를 담을 Queue를 하나 생성하자.
그리고 1부터 N까지의 수를 Queue에 삽입해둔다.

while(qu.size() != 1) {
    qu.poll();
    int front = qu.poll();
    qu.offer(front);
}
bw.write(qu.peek()+"\n");

마지막으로 큐의 삽입된 값이 1개가 될 때까지 큐에서 값을 2번 추출하는데, 1번째 추출은 삭제를 의미한다.
2번째 추출된 값을 큐에 다시 삽입하면 된다. 이 값을 맨 뒤로 추출하는 이유는 큐는 선입선출 방식이기에 가장 최신에 넣은 값이 결국 맨 뒤의 값이기 때문이다.

작성코드

---

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

class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        Queue<Integer> qu = new LinkedList<>();

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

        while(qu.size() != 1) {
            qu.poll();
            int front = qu.poll();
            qu.offer(front);
        }
        bw.write(qu.peek()+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 큐 2 문제와 동일하게 Queue 인터페이스 자체로 푸는 방식도 좋지만, LinkedList나 Deque를 통해서도 꼭 풀어볼 예정이다.

출처

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.