[C++] 백준(BOJ) 1158 요세푸스 문제

예지 출력은 잘 나왔는데, 계속 '시간초과' 오류가 났다.

'시간초과' 오류가 난 코드는 풀이1 이다.

 

풀이1(내 풀이)

• 풀이1에서 queue 의 rear와 front 정의, Dequeue() 함수의 정의를 내맘대로 바꾸었다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Queue {
public:
    int N;
    int K;
    int front, rear;
    int* data; // Removed initialization here

public:

    Queue(int n, int k) {
        K = k;
        N = n + 1;
        front = rear = 0;
        data = new int[N]; // Initialize data array after setting N
    }

    bool isEmpty() {
        int result = 0;
        for (int i = 0; i < N; i++) {
            result += data[i];
        }
        if (result == 0)
            return true;
        else
            return false;
    }

    void enqueue(int v) {
       
        data[rear % N] = v;
        rear++;
    }

    void dequeue() {
        int count = 0;
        while (count < K && !isEmpty()) {
            front = (front + 1) % N;
            while (data[front] == 0)
            {
                front = (front + 1) % N;
            }

            count++;
        }
        data[front] = 0;
    }

    ~Queue() { delete[] data; } // Added destructor to free memory
};

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N, K;
    cin >> N >> K;

    vector<int> ans;
    Queue que(N,K);
    for (int i = 0; i <= N; i++) {
        que.enqueue(i);
    }
    
   
    while (!que.isEmpty()) {
        que.dequeue();
        ans.push_back(que.front);
    }

    string answer = "<";
    for (int i = 0; i < N; i++) {
        answer += to_string(ans[i]);
        if (i != N - 1)
            answer += ", ";
        else
            answer += ">";
    }

    cout << answer;
    return 0;
}

 

풀이2 (내 풀이)

• Que라는 새로운 class를 만들어서 K의 배수 번째 수가 아니면, Que의 data 멤버에서 삭제만 하고, K의 배수 번째 수가 맞으면, Que의 data 멤버에서 삭제하고 ans에 추가한다
• 처음에 돌렸을때 시간초과가 나서 이를 방지하기 위해 ans를 vector에서 string으로 수정했다

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Que {
protected:
    int front;
    vector<int> data;
    int N;

public:
    Que(int n) {
        N = n;
        front = 0;
        for (int i = 0; i < N; i++)
            data.push_back(i + 1);
    }

    bool empty() {
        return N == 0;
    }

    void pop_front() {
        if (!empty()) {
            front = (front + 1) % data.size();
            N--;
        }
    }

    void push_back(int a) {
        data.push_back(a);
        N++;
    }

    int first_element() {
        return data[front];
    }

    int size() {
        return N;
    }
};

int main() {
    int N, K;
    cin >> N >> K;
    Que q(N);
    string ans = "<";
    int time = 0;

    while (!q.empty()) {
        if (q.size() == 1) {
            int a = q.first_element();
            q.pop_front();
            ans += to_string(a);
            ans += ">";;
        }
        else if (time % K == (K - 1)) {
            int a = q.first_element();
            q.pop_front();
            ans += to_string(a);
            ans += ", ";
        }
        else {
            q.push_back(q.first_element());
            q.pop_front();
        }
        time++;
    }

    cout << ans+"\0";

    return 0;
}

 

풀이3 (다른 사람)

• Queue 큐 STL을 사용한 문제 풀이다. 
• 풀이2 에서와 같이 복잡하게 while문 내에 if 조건문들을 사용할 필요없이, K-2번 만큼만 Queue의 뒤로 보내고 K-1번 째마다 정답 Vector에 push해주면 된다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
    int n, k;
    vector<int> v;
    queue<int> q;
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        q.push(i);
    }
    while(!q.empty()){
        for (int i = 0; i < k-1; i++){
            q.push(q.front()); // 자기 차례가 아닌 경우 수를 뒤로 보냄
            q.pop();
        }
        v.push_back(q.front());//차례 도달 시
        q.pop();
    }
    cout << "<";
    for (int i = 0; i < n-1;i++){
        cout << v[i] << ", ";
    }
    cout << v[n - 1] << ">";
    return 0;
}

---