Lv.1queuesimulation
마지막 남는 카드
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
1부터 n까지 번호가 적힌 카드 n장이 한 줄로 쌓여 있습니다. 맨 위에는 1번, 맨 아래에는 n번 카드가 있습니다.
카드가 한 장 남을 때까지 다음 동작을 반복합니다.
- 맨 위의 카드를 버립니다.
- 그다음 맨 위에 있게 된 카드를 맨 아래로 옮깁니다.
마지막에 남는 카드의 번호를 반환하세요.
입출력 예
| n | result |
|---|---|
4 | 4 |
6 | 4 |
1 | 1 |
입출력 예 설명
예 1 — 위에서부터 1 2 3 4 → 1을 버리고 2를 아래로: 3 4 2 → 3을 버리고 4를 아래로: 2 4 → 2를 버리면 4가 남습니다.
예 2 — 1 2 3 4 5 6 → 3 4 5 6 2 → 5 6 2 4 → 2 4 6 → 6 4 → 4.
예 3 — 처음부터 한 장뿐입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int) → int
제한 사항
-
n
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| n | 기대 출력 |
|---|---|
4 | 4 |
6 | 4 |
1 | 1 |
힌트
힌트
맨 앞에서 꺼내고 맨 뒤에 넣는 동작은 큐가 가장 잘하는 일입니다. 큐를 쓰면 한 번의 동작이 이고, 동작마다 카드가 한 장씩 줄어드므로 전체 입니다.
배열의 맨 앞 원소를 지우는 연산(erase(begin), pop(0), remove(0) 등)은 나머지 원소를 모두 한 칸씩 당기므로 입니다. 이것을 번 하면 이 되어 효율성 테스트에서 시간 초과가 납니다.
더 생각해 보고 싶다면, 작은 n에 대한 답을 나열해 규칙을 찾아보세요. 반복 없이 바로 계산하는 식도 있습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 3 | 판정만 |