백준2164 카드2

작성일 | In

문제 링크

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

사용 알고리즘

  • 큐

시간복잡도

  • O(n)

풀이

https://justicehui.github.io/2018/06/10/BOJ2161.html
이 문제와 거의 동일한 문제이니 이 글을 먼저 읽고 와주시기 바랍니다.

바로 해결방법을 적어보겠습니다.

  1. 마지막에 나올 값을 저장할 변수 ans 선언
  2. n 입력
  3. 1부터 n까지의 수를 queue에 삽입
  4. ans에 q.front() 저장
  5. q.pop()
  6. q.front()의 값을 push
  7. q.pop()

3번에서 ans에 q.front()를 저장하는 이유는 가장 최근에 나온 카드를 계속 갱신해서 마지막으로 나온 카드를 최종적으로 출력하기 위해 q.front() 를 저장합니다.

전체 코드

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

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