1. 선형자료구조 - 조세퍼스 문제(1158)

1. 사람들이 원을 이루며 앉아 있다 -> 처음과 끝이 없이 이어져있다.

2. 일정한 규칙을 두고 중간의 원소들이 삭제 된다. -> 특정 위치의 원소 삭제가 수행되어야 한다. -> 배열보다 연결리스트가 유리

위의 생각의 흐름으로 이 문제는 원형 연결리스트로 해결할 수 있다.

c++에는 원형 연결 리스트를 따로 제공하지 않으므로 STL의 List로 구현하도록 한다.

List Container

list container는 시퀀스 컨테이너의 일종으로, 순서를 유지하는 구조이다.

노드 기반 컨테이너이며, doubly linked list 라고 생각하면 된다.

원소 탐색 시 인덱스를 통한 임의 접근은 불가능하고, 양방향 탐색자( ++, -- )를 통해 가능하다.

#include <list>

using namespace std;

int main() {

List<int> lt;  // int형 리스트 컨테이너 생성 (비어있음)

List<int>::iterator iter;  // int형 리스트 컨테이너의 iterator

}

List를 사용하기 위한 기본 세팅은 위와 같다.

iterator는 List의 노드들을 돌아가면서 가리키는 반복자이다.

*iter : iterator가 현재 가리키고 있는 노드의 원소를 리턴한다.

문제 풀이

#include <iostream>

#include <list>

#include <vector>

using namespace std;

int main() {

int n; //인원수

int m; // 규칙 숫자

int a = 0; // 순열 입력 인덱스

vector<int> result; //조세퍼스 순열

list<int> lt; 

list<int>::iterator iter;

cin >> n;

cin >> m;

result.reserve(n);

// 연결리스트 초기화

for (int i = 1; i < n + 1; i++) {

lt.push_back(i);

}

iter = lt.begin();

while (1) {

if (n == 1) {

result.push_back(*iter);  // 마지막 남은 사람 순열에 저장

break;

}

// 해당 순서 사람 찾기

for (int i = 0; i < m - 1; i++) {

iter++;

if (iter == lt.end())

iter = lt.begin();

}

// 조세퍼스 순열에 제거할 사람 입력

result.push_back(*iter);

a++;

// 순서에 해당하는 사람 제거

iter = lt.erase(iter);

if (iter == lt.end())

iter = lt.begin();

n--;

}

cout << "<";

for (vector<int>::size_type i = 0; i < result.size()-1; i++) {

cout << result[i] << ", ";

}

cout << result[result.size()-1] << ">";

return 0;

}

lt.push_back() : lt List의 마지막에 원소 삽입

p = lt.erase(q) : q가 가리키는 원소 삭제 후 p에 다음 원소 리턴

lt.begin() : lt List의 시작 iterator 리턴

lt.end() : lt List의 마지막 iterator 리턴(마지막 원소의 다음을 가리킴)