안녕하세요!
오늘 문제는 백준 2164번, 카드2라는 문제입니다.
자! 집중해볼까요?
1. 오늘의 학습 키워드
- 큐
- 구현
2. 문제: 카드2 (2164번)
- 단계: 🥈실버 4티어
- 알고리즘 분류: 자료 구조, 큐
- 출처: https://www.acmicpc.net/problem/2164
카드2
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 128 MB | 132081 | 68518 | 53357 | 50.819% |
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
예제 입력 1 복사
6
예제 출력 1 복사
4
알고리즘 분류
3. 나의 풀이
문제 접근 방식
이 문제는 큐(Queue) 자료구조를 활용하여 해결할 수 있습니다. 큐는 선입선출(FIFO, First-In-First-Out) 구조로, 가장 먼저 들어온 요소가 가장 먼저 나가는 특성을 가지고 있습니다.
문제에서 제시된 동작은 다음과 같습니다:
- 제일 위에 있는 카드를 버립니다. (큐에서 첫 번째 요소를 제거)
- 그 다음 제일 위에 있는 카드를 제일 아래로 옮깁니다. (큐에서 첫 번째 요소를 제거하고, 그 요소를 큐의 맨 뒤로 추가)
이 과정을 반복하여 카드가 한 장 남을 때까지 진행하면 됩니다.
코드 설명
import sys
from collections import deque
# 입력받은 N을 정수로 변환
N = int(sys.stdin.readline().strip())
# 1부터 N까지의 숫자를 deque로 생성
card = deque([i for i in range(1, N+1)])
# 카드가 한 장 남을 때까지 반복
while len(card) > 1:
card.popleft() # 제일 위의 카드를 버림
card.append(card.popleft()) # 제일 위의 카드를 제일 아래로 옮김
# 마지막 남은 카드 출력
print(card[0])
코드 동작 원리
- 큐 초기화:
deque([i for i in range(1, N+1)])을 통해 1부터 N까지의 숫자를 차례대로 가진 큐를 만듭니다.
- 카드 제거와 이동:
while len(card) > 1:루프는 카드가 한 장 남을 때까지 반복됩니다.card.popleft()는 큐의 첫 번째 요소(제일 위의 카드)를 제거합니다.card.append(card.popleft())는 다음 첫 번째 요소를 제거한 후, 그 값을 큐의 맨 뒤에 추가하여 제일 아래로 옮깁니다.
- 결과 출력:
- 마지막 남은 카드의 번호를
print(card[0])로 출력합니다.
- 마지막 남은 카드의 번호를
시간 복잡도 분석
- 큐 초기화:
O(N)-deque를 생성할 때 1부터 N까지의 요소를 추가하는 작업. - 반복문: 각 반복에서
popleft()와append()연산이 발생하며, 이 두 연산은 모두O(1)시간 복잡도를 가집니다.- 이 반복은 N-1번 반복되므로, 반복문 전체의 시간 복잡도는
O(N)입니다.
- 이 반복은 N-1번 반복되므로, 반복문 전체의 시간 복잡도는
따라서, 이 알고리즘의 전체 시간 복잡도는 O(N)입니다.
공간 복잡도 분석
deque에 저장된 요소의 개수는 최대 N개이므로, 공간 복잡도는O(N)입니다.
이 코드의 시간 복잡도와 공간 복잡도 모두 O(N)으로, 주어진 문제 크기(최대 500,000)에 대해 효율적인 풀이입니다. 큐를 사용하여 문제의 요구사항을 간단하게 해결할 수 있었습니다.
마무리
문제를 얼핏보면 스택 자료 구조 유형인가? 생각하실 수 있습니다. 하지만 선입 선출의 원리만 파악이 된다면, 선입 선출을 그대로 구현하는 문제였습니다.
내일도 새로운 문제로 찾아오겠습니다.
읽어주셔서 감사합니다.
매일 발전하는 개발자가 될거야!!⭐
