Written by JS970
on February 7, 2023

11866 - 요세푸스 문제 0

난이도: 실버 5
날짜: 2023년 2월 7일
상태: Correct
추가 검토 여부: Yes

solution

이 문제를 해결하기 위해 queue를 사용하여 차례에 맞는 숫자를 pop하는 방식을 사용했다. 차례에 맞지 않는 경우 pop후 다시 push하여 circle을 구현하였다.
처음에는 deque를 통해 구현하려 했는데, 처음 코드처럼 코딩할 것면 굳이 deque가 아니라 queue로 충분하다…
이 문제에서 double-free segmentaion fault로 인해서 많은 시간을 사용하였다…
- double-free segmentation fault는 동적할당한 변수 또는 배열에 대해 delete가 두 번 이상 수행될 경우 발생하는 런타임 에러이다.
- c++에서는 복사 생성자를 컴파일러가 자동으로 생성하는 과정에서 자주 발생한다고 한다.(ref참조)
- 첫 시도에서 tmp에 pop하기 전의 front를 저장하고, pop수행 후 이 값을 다시 push하는 식으로 구현하였는데 이 과정에서 dobule-free error가 발생했다.
- 이를 먼저 push한 후 pop하는 코드로 수정하니 에러가 사라졌다.
- 솔직히 정확한 원인에 대해서는 잘 모르겠다. 본 코드에서 직접 동적 할당을 사용한 적도 없고 stl을 사용했는데도 이런 에러가 발생했다.
- 심지어 항상 발생하는 것이 아니라 특정 입력에 대해서만 이런 에러가 발생해서 더욱 찾기 힘들었다.
- 그냥 이런 상황 자체를 경험적으로 학습해야 할 듯 하다…

code

오답 코드

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

int main()
{
    int N, K;
    cin >> N >> K;
    deque<int> deque;
    for(int i = 0; i < N; i++)
        deque.push_back(i+1);

    int idx = K-1;
    vector<int> ans;

    for(int i = 0; i < K-1; i++)
    {
        int tmp = deque.front();
        deque.pop_front();
        deque.push_back(tmp);
    }
    while(deque.size() > 0)
    {
        ans.push_back(deque.front());
        deque.pop_front();
        for(int i = 0; i < K-1; i++)
        {
            int tmp = deque.front();
            deque.pop_front();
            deque.push_back(tmp);
        }
    }
    cout << "<";
    int i;
    for(i = 0; i < N-1; i++)
        cout << ans[i] << ", ";
    cout << ans[i] << ">" << endl;

    return 0;
}

수정 코드(정답)

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

int main()
{
    int N, K;
    cin >> N >> K;
    queue<int> queue;
    for(int i = 0; i < N; i++)
        queue.push(i+1);

    int idx = K-1;
    vector<int> ans;

    for(int i = 0; i < K-1; i++)
    {
        queue.push(queue.front());
        queue.pop();
    }
    
    while(queue.size() > 0)
    {
        ans.push_back(queue.front());
        queue.pop();
        for(int i = 0; i < K-1; i++)
        {
            queue.push(queue.front());
            queue.pop();
        }
    }
    cout << "<";
    int i;
    for(i = 0; i < N-1; i++)
        cout << ans[i] << ", ";
    cout << ans[i] << ">" << endl;

    return 0;
}

ref

11866번: 요세푸스 문제 0

Double free or corruption after queue::push

Top