[백준 1158] 요세푸스 문제 - C++ / 알고리즘 '연결 리스트'

문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

나의 코드 - 시간초과...

(c++를 이제 본격적으로 시작해서 아직 감이 안온다 ㅠㅠ)

 

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

int main() {
	int n, k, count;
	list::iterator itr;

	cin >> n >> k;
	
	list lst;

	//1~n번까지 숫자넣기
	for (int i = 1; i <= n;i++) {
		lst.push_back(i);
	}

	//k번째 사람 출력하고 삭제하기
	cout << "<";
	count = 1;
	itr = lst.begin();
	while (lst.size() != 0) {
		if (itr == lst.end())   //이미 한반퀴를 돌았다면
			itr = lst.begin();
		
		if (count == k) {  //k번째 요소라면
			cout << *itr;

			count = 1;
			itr  = lst.erase(itr); //erase 함수의 반환값이 삭제 원소 다음에 있는 원소의 반복자
			if (itr == lst.end())
				itr = lst.begin();

			if (lst.size() != 1) {
				cout << ", ";
			}
			else {  //삭제했더니 원소가 하나밖에 안 남으면
				itr = lst.begin();
				cout << ", " << *itr;
				break;
			}
		}
		count++;
		itr++;
	}
	cout << ">";
}

 

수정 코드

참고 사이트: https://numerok.tistory.com/135

백준 1158 조세퍼스 문제 [C++]

문제점:

1. count라는 변수로 일일이 새지 말고 for문을 이용해서(k-1번 반복!!!!) 한꺼번에 돌리자 - if문이 너무 많다!!!!

2. while문 조건에 size != 1를 넣어서 따로 빼자... break를 쓸거면 왜 while조건을 붙였니???

 

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

int main() {
	int n, k;
	list::iterator itr;

	cin >> n >> k;
	
	list lst;

	//1~n번까지 숫자넣기
	for (int i = 1; i <= n;i++) {
		lst.push_back(i);
	}

	cout << "<";
	itr = lst.begin();
	while (lst.size() != 1) {
    	//k번째 요소 찾기
		for (int i = 0; i < k - 1; i++) {
			itr++;
			if (itr == lst.end())   //이미 한반퀴를 돌았다면
				itr = lst.begin();
		}
		cout << *itr << ", ";  //k번째 요소 출력
		itr = lst.erase(itr); //(중요)erase 함수의 반환값이 삭제 원소 다음에 있는 원소의 반복자
		if (itr == lst.end())  //끝의 요소 다음이 lst.end()인 경우
			itr = lst.begin();
	}
	cout << *itr << ">";
}

 list 의 erase함수의 반환값은 삭제 원소 다음에 있는 원소의 반복자이다.