백준 #1158

난이도:★☆☆☆☆☆☆☆☆☆

이번 문제부터는 그냥 내가 느낀 난이도를 표시해보려고 한다. 나중에 다시 풀 때 조절하면 되니까..                                       

---

문제 접근 방법

음 이번 주차 과제 이전에 풍선 터트리기 문제를 실패했는데 그 문제와 뭔가 비슷한 느낌이 들어서 list로 풀면 좋을 것 같았다. n번째 수를 잡아서 출력하는 건데 list안에서 이동시키면서 이미 지나온 위치는 0으로 바꾸고 0인 위치는 무시해주고, 만약 iterator가 마지막에서 오른쪽으로 이동하려고 하면 처음으로 이동시켜주었다.

이 문제 역시 크게 어려웠던 점이 없었기 때문에 주석으로 표시하겠습니다

#include<iostream>
#include<list>
using namespace std;
int main() {
	list<int>circle; 
	int N,K; //배열의 수, n번째 수
	cin >> N;
	for (int i = 1; i <= N; i++) {
		circle.push_back(i);
	}

	list<int>::iterator iter;
	iter = circle.begin();

	cin >> K; //n번째 수
	for (int i = 0; i < K - 1; i++) { //n번째 위치로 이동
		iter++;
	}
	cout << "<"; 
	/*
	1. *iter(n번째수)를 출력
	2.n번이동
	2-1. 0이 있는자리는 없다고 취급하고 한칸더 이동
	2-2. 만약 마지막에서 오른쪽으로 가야한다면 처음으로 이동시킴
	*/
	while (N--) {
		if (N == 0) { //마지막엔 ,를 출력하지 않기위해서
			cout << *iter;
			break;
		}
		else {
			cout << *iter << "," << " ";
		}
		*iter = 0; //각 반복바다  n번째 위치의 수를 0으로 변경->삭제비스무리한거
		for (int k = 0; k < K; k++) { //3번째수라면 3번 반복
			iter++;       //일단 한칸 옮겨주고
			if (iter == (circle.end())) {  //옮긴게 마지막이네? 처음으로 보냄
				iter = circle.begin();
			}
			if (*iter == 0) { //해당 위치를 지나감
				while (*iter == 0) { //0일때 싹 다 지나감
					iter++;
					if (iter == (circle.end())) { 
						iter = circle.begin();
					}

				}
			}

		}
		
	}
	cout << ">";
}

시간 복잡도:O(n)이다. 입력과 while문안에서 처리하는 내용들도 모두 상수 시간에 되므로 O(n).