백준 1158 - 요세푸스 문제 (C++)

 

 

1~N 명이 앉아있고, 1부터 시작해서 K번째에 있는 사람을 제거하는 문제이다.

예를 들어, N이 10이고 K가 3이라고 가정하자.

 

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 1

 

이런 식으로 순서대로 10명이 앉아있으며, 원형이기 때문에 마지막 10번 사람의 옆엔 1번이 위치하게 된다.

K가 3이라면, 맨 처음 3번째에 존재하는 3이 제거된다.

 

1 - 2 - 공석 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 1

 

3이 제거되었고, 기존 3의 자리는 공석이 되었으므로 사람들의 위치관계를 정리하면 위와 같이 된다.

3의 기존 자리를 기준으로 다시 K번만큼 수를 세고 나면, 6번이 선택되므로 다음은 6번이 제거된다.

 

1 - 2 - 공석 - 4 - 5 - 공석 - 7 - 8 - 9 - 10 - 1

 

동일하게, 반복하면 다음은 9번이 제거되며, 그 다음은 2번이 제거된다. 계속 반복하여 모두 제거될 때 까지 진행하면 된다.

 

문제를 푸는 방법은 여러가지가 있겠지만, 본인은 std::list를 활용하여 해결하였다.

처음엔 std::vector를 이용하여 공석을 모두 고려하여 해결하였지만, 매 탐색마다 공석의 위치를 고려하는 것 때문에 제출 후 시간이 830ms 정도가 나왔다.

이후, list를 이용하여 공석을 모두 제거하고 남아있는 사람만을 기준으로 탐색을 하게 되니, 100ms까지 줄어들었다.

 

---

문제 해결

먼저 입력과 초기화에 관한 코드이다.

int N = 0;
int K = 0;

std::cin >> N >> K;

std::list<int> Person(N);
std::list<int>::iterator Iter = Person.begin();

int PersonIndex = 1;
while (Iter != Person.end())
{
    *Iter = PersonIndex;

    Iter++;
    PersonIndex++;
}

 

N과 K를 입력받았고, N의 크기만큼 list를 resize하였다.

이후, List를 순회하며 값을 1~N까지 순서대로 입력해주었다.

std::queue<int> Delete;

int Count = 1;
Iter = Person.begin();

while (Delete.size() < N)
{
    if (Iter == Person.end())
    {
        Iter = Person.begin();
    }

    if (Count == K)
    {
        Count = 0;
        Delete.push(*Iter);
        Iter = Person.erase(Iter);
        Count++;

        continue;
    }

    Iter++;
    Count++;
}

 

 

문제 해결 코드이다.

먼저, 제거된 사람들을 순서대로 출력하는 것이 문제의 목표이기 때문에,

제거되는 사람들을 순서대로 queue에 집어넣고 추후 pop하여 순서대로 출력하기 위해 queue를 하나 선언하였다.

 

이후, Iterator를 돌며 순회하였다. 순회하면서 Count 를 1씩 증가시키며 몇 번을 건너뛰었는지 계산한 뒤, 이 값이 k와 같다면 해당 사람을 제거하였다.

 

맨 끝 지점의 사람의 옆엔 첫번째 사람이 앉아있는 원탁구조이기 때문에, 이터레이터가 end를 가리킬 때엔 값을 begin으로 변경해주었다.

 

이후, 모두 제거되었을 때 반복문이 종료된다.

모두 제거되는 조건을 list의 size() 가 0일 때로 계산할 수도 있지만, 본인은 queue의 size (제거된 사람의 수)가 전체 인원 수와 동일해질 때 반복문을 종료하였다.

 

std::cout << "<";
while (Delete.size() > 0)
{
    int CurIndex = Delete.front();
    Delete.pop();

    std::cout << CurIndex;

    if (Delete.size() > 0)
    {
        std::cout << ", ";
    }
}

std::cout << ">";

 

다음은 출력이다.

출력을 <1, 2, 3, 4, 5 > 이런 식으로 출력해야 하기 때문에

처음엔 <를 출력하고 끝엔 >를 출력하였다.

이후 원소를 하나씩 출력하였고, 마지막 원소를 제외하고는 모두 원소를 출력한 뒤에 ", "를 추가로 출력해주었다.

 

아래는 전체 코드이다.

int main()
{
	int N = 0;
	int K = 0;

	std::cin >> N >> K;

	std::list<int> Person(N);
	std::list<int>::iterator Iter = Person.begin();
	
	int PersonIndex = 1;
	while (Iter != Person.end())
	{
		*Iter = PersonIndex;
		
		Iter++;
		PersonIndex++;
	}

	std::queue<int> Delete;
	
	int Count = 1;
	Iter = Person.begin();

	while (Delete.size() < N)
	{
		if (Iter == Person.end())
		{
			Iter = Person.begin();
		}

		if (Count == K)
		{
			Count = 0;
			Delete.push(*Iter);
			Iter = Person.erase(Iter);
			Count++;

			continue;
		}

		Iter++;
		Count++;
	}

	std::cout << "<";
	while (Delete.size() > 0)
	{
		int CurIndex = Delete.front();
		Delete.pop();

		std::cout << CurIndex;

		if (Delete.size() > 0)
		{
			std::cout << ", ";
		}
	}

	std::cout << ">";

	return 0;
}

 

 

다른 사람들과 비교했을 때, 썩 빠른 코드는 아니라서 조금 더 고민을 해볼 필요가 있을 것 같다.