백준2161 카드1

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/2161

사용 알고리즘

  • 큐

시간복잡도

  • O(n)

풀이

맨 위 카드를 버리고(그 후 출력) 그 다음 위에 있는 카드를 맨 아래로 보내는 과정을 큐 를 이용해 구상해보자면,

  1. front를 출력한 뒤 pop
  2. pop한 것을 push 처럼 해결할 수 있습니다.

조금 더 구체적으로 풀이 방법을 생각해봅시다.

  1. n 입력
  2. 1부터 n까지의 수를 queue에 삽입
  3. q.front() 출력
  4. q.pop()
  5. q.front()의 값을 q.push() 하고
  6. q.pop()
  7. 3번부터 6번 항목을 q.empty()가 false인 동안 반복

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main(){
    queue<int> q;
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) q.push(i);
    while(!q.empty()){
        printf("%d ", q.front());
        q.pop();
        int poped = q.front();
        q.pop();
        q.push(poped);
    }
}