C++) 백준 2161, 카드1

문제 링크 https://www.acmicpc.net/problem/2161

 

문제 내용

카드에 1~n까지 쓰여있는 카드 n장이 있다.

1. 가장 위의 카드를 버린다.

2. 그 다음 위에 있는 카드를 맨 밑으로 넣는다.

규칙 1, 2를 반복하고 출력으로 버려지는 카드를 순서대로 출력하고, 마지막에 남는 카드까지 출력한다.

 

코드

#include<iostream>//2161, 카드1
#include<queue>
using namespace std;
queue<int>q;
int n;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    while (q.size()!=1) {
        cout<<q.front()<<" ";
        q.pop();
        q.push(q.front());
        q.pop();
    }
    cout<<q.front();
    return 0;
}

 

 

풀이 및 분석

이 문제를 큐를 사용해야하며, 큐를 사용하기 위해서는 #include<queue>를 사용 또는 #include<bits/stdc++.h>를 사용한다.

#include<bits/stdc++.h>는 자주 사용되는 헤더 파일을 한 번에 포함하는 헤더로 비공식이긴하나 여러 곳에서 사용된다.

 

1~n까지의 값을 큐에 넣으려면 for를 돌리면서 그때의 i값을 넣어서 큐의 구조상 가장 위에는 1, 가장 아래에는 n을 위치시킨다.

가장 마지막에 남은 카드를 확인해야함으로 while으로 q.size가 1이 아닐때까지 반복한다.

q.front으로 큐의 맨 앞 카드를 가져와서 출력하고 q.push(q.front())으로가장 맨 앞에 카드를 맨 뒤로 이동시킨다.

이는 버려지는 카드이기에 처리한 맨 앞 카드를 pop을 통해 처리한다.

이가 끝나면 마지막 한장이 남아있으므로, cout<<q.front를 활용해 마지막 카드를 출력한다.