[백준] 2164번 카드2 (Python,C++)

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

2164번: 카드2

 

아주 쉽지만 자료구조의 중요성을 느낄 수 있었던 문제이다.

해당문제는 리스트를 이용하면 시간초과가 나온다.

 

1. 맨앞값 삭제 O(N)

2. 맨앞의 값을 맨뒤로 보내기 (삽입,삭제) O(N) X 2

 

이짓을 1이 남을때까지,즉 N-1번반복하면 N-1 X O(N) 총 복잡도는 O(N^2)이 된다.

따라서 해당문제는 시간복잡도 O(1)인 queue를 이용한다.

---

SOLUTION CODE

# PYTHON

from collections import deque

N = int(input())
dq = deque(range(1,N+1))

while len(dq) > 1: // 두개이상일때까지반복
    dq.popleft()
    dq.append(dq.popleft())
    
print(dq.popleft())

 

# C++

#include <iostream>
#include <queue>

using namespace std;

int main(int argc,char**argv){
    ios::sync_with_stdio(0);
	cin.tie(0);

    queue<int> q;
    int N;

    cin >> N;

    for(int i=1;i<=N;i++){
        q.push(i);
    }

    while(q.size()>1){
        q.pop();
        q.push(q.front());
        q.pop();
    }

    cout << q.front();
    return 0;

}