[Baekjoon/백준] 1158번: 요세푸스 문제 0_deque(C/C++)

 

 

※ 이번 문제에서 알게된 점

§ insert() 함수

dq.insert함수는 insert(pos, val);로 값이 들어가야 해서 dq.insert(dq.end()+i, dq.begin()+i);처럼 사용하지 말아야 한다.

위와 같은 의미로 다시 코드를 짜고 싶다면 다음과 같이 dq.insert(dq.end()+i, dq[i]); 와 같이 사용해야 한다.

dq.insert(dq.end()+i+1, dq[i]); // 정상적인 작동
dq.insert(dq.end()+i+1, dq.begin(i));  // dq.begin(i) 부분에 오류발생
dq.insert(dq.end()+i+1, dq.begin()+i); // dq.insert() 부분에 오류발생

 

 

 

§ front 와 begin 의 차이

가장 고생했던 부분이 있는데 다음과 같다.

 

<정답코드>

for (int i = 0; i < k-1; i++) {
    dq.push_back(dq.front());
    dq.pop_front();
}
cout << dq.front() << ", ";
dq.erase(dq.begin());

// 7 3
// <3, 6, 2, 7, 5, 1, 4>

 

<오답코드>

for (int i = 0; i < k; i++) {
    dq.insert(dq.end()+i+1, dq[i]);
    dq.erase(dq.begin()+i);
}
dq.pop_back();

// 7 3
// <2, 4, 7, 7, 7, 7, 7>

 

front()는 첫 "요소"를 반환하는 것이다.

begin()은 그 요소의 참조 즉, "주소값"을 반환한다.

즉, begin은 컬렉션을 통해 반복하는 데 사용할 수 있는 해당 요소의 iterators를 반환하지만

      front는 컬렉션의 첫 번째 요소에 대한 참조만 반환 (포인터 개념)합니다.

 

따라서 push_back(값); 메소드를 활용하기 위해서는 front를 사용하는 것이 좋다.

dq.push_back(dq.front());

 

 

 

 

 

 

§ my solution 

추출,삽입이 빠른 덱으로  k - 1번씩 밀고, 맨 앞에있는 값을 제거하는 알고리즘을, 모든 값이 없어질 때 까지 반복

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

deque<int> dq;
int main(){
    int n, k;   cin >> n >> k;
    cout << '<';


    for (int i = 0; i < n; i++) {
        dq.push_back(i+1);
    }
    while (dq.size() > 1) {
        for (int i = 0; i < k-1; i++) {
            dq.push_back(dq.front());
            dq.pop_front();
        }
        cout << dq.front() << ", ";
        dq.erase(dq.begin());
    }
    cout << dq[0];
    cout << '>';
}

 

 

§ 시행착오 

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

deque<int> dq;
int main(){
    int n, k;   cin >> n >> k;
    cout << '<';


    for (int i = 0; i < n; i++) {
        dq.push_back(i+1);
    }
    while (dq.size() > 1) {
            if (dq.size() > 2) {
                cout << dq[k-1] << ", ";
                for (int i = 0; i < k; i++) {
                    dq.insert(dq.end()+i+1, dq[i]);
                    dq.erase(dq.begin()+i);
                }
                dq.pop_back();
            }
            else if(dq.size() <= 2){
                cout << dq[0] << ", "<< dq[1];
                break;
            }
    }
    cout << dq[0];
    cout << '>';
}

왜 이따구로 풀었을까?

 

- 일단 먼저 다음과 같이 접근하였다.

1 2 3 4
                    7  6  5

             front                  back <-- 삽입
                    1 2 3 4 5 6 7
                    (1 2 3) 4 5 6 7 [1 2 3]
                    4 5 6 7 1 2
                    (4 5 6) 7 1 2 [4 5 6]
                    7 1 2 4 5
                    4 5 7 1
                    1 4 5
                    4 5 1
>> 그대로 출력       5 1 4

왜 안될까?  => k값이 3이라 저렇게 출력되는 것처럼 보일 뿐, 다음과 같은 테스트 케이스에서는 오답으로 나온다.

10 1
<1, 2, 3, 4, 5, 6, 7, 8, 9, 10>

5 5
<5, 1, 3, 4, 2>

10 4
<4, 8, 2, 7, 3, 10, 9, 1, 6, 5>

따라서 예제의 특수성에 빠지지 않도록 조심할 것!