[99클럽 16일차] [백준] 2161 카드1

백준 2161 카드 1

❓ 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

문제를 아주 간단히 정리하자면 위 처럼 요약할 수 있다.

주어진 정수 N을 받아서 1부터 N까지의 숫자가 적힌 카드 덱을 만든다. 맨 윗 장을 제거하고, 그 다음장은 카드 맨 밑으로, 또 윗 장을 제거하고 다음장은 맨 밑으로.. 이런 식으로 반복하여 제거되는 카드의 번호를 출력해야한다.

LinkedList로 풀기

LinkedList로 카드 덱을 구현했다. 앞에서 카드 한 장을 버리고 맨 뒤로 넣어야하기 때문에 맨 처음 맨 뒤의 순서가 중요하다고 생각해서 이런식으로 코드를 작성했다.

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());
      List<Integer> list = new LinkedList<>();  // LinkedList 사용으로 앞쪽 요소 제거 및 추가 용이

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

      while (list.size() > 1) {  
          // 첫 번째 카드를 버리고 결과에 추가
          bw.write(String.valueOf(list.get(0)) + " ");
          list.remove(0);

          // 두 번째 카드를 맨 뒤로 보내기
          int lastIndex = list.size();
          list.add(lastIndex, list.get(0));
          list.remove(0);
      }
      
      // 마지막 남은 카드 추가
      bw.write(String.valueOf(list.get(0)));

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

시간 복잡도를 고려해본다면 이 방법은 효율적이지 않다.

이 코드의 경우 remove(0)를 반복적으로 사용하므로, 리스트의 크기가 커질수록 전체 시간 복잡도는 O(N^2)에 가까워질 수 있다.

이 문제에서는 입력 크기 제한(N(1 ≤ N ≤ 1,000))이 크지 않기 때문에 LinkedList를 통한 해결이 가능했지만 만약 입력이 더 커진다면 Queue를 사용하는 방식이 더 효율적일 것이다.

Queue로 풀기

public static void main(String[] args) {
    int N = 10; // 입력을 10이라고 친다면
    Queue<Integer> queue = new LinkedList<>();
    
    for (int i = 1; i <= N; i++) {
        queue.add(i);
    }
    
    StringBuilder result = new StringBuilder();
    
    while (queue.size() > 1) {
        result.append(queue.poll()).append(" ");
        queue.add(queue.poll());
    }
    
    result.append(queue.poll());
    System.out.println(result);
}

Queue가 적합한 이유

1. 순환구조
   • Queue는 선입선출이기 때문에 poll()로 요소를 제거해가면서 순환 구조를 쉽게 구현할 수 있다.
2. 작업 순서 유지
   • 추가한 순서를 그대로 유지하면서 작업을 수행한다.
   • 순서 기반 문제에서 아주 적합함..!!
3. 재삽입 용이
   • poll()로 꺼낸 요소를 다시 add()할 수 있다.
   • 꺼내서 다시 덱에 집어넣는다. → Queue를 떠올릴 것.

순서대로 제거하고, 다시 맨 뒤로 보내는 작업을 봤을 때 바로 Queue를 떠올리지 못한 것은.. 아직 내가 Queue와 Stack에 익숙치 않아서 일까? 😞

문제를 보고 적절한 자료구조를 택하는 것이 중요하니 빠르게 자료구조 예제를 풀어보면서 언제 어디서 쓰여야 적합한지를 알아봐야겠다..!!