[BOJ/백준] 1158 요세푸스 문제

[BOJ/백준] 1158 요세푸스 문제

● [문제번호 1158] 요세푸스 문제

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

● 알아야 할 것

: list 자료구조와 메소드

● 풀이 과정

: 주된 작업이 삭제 연산이므로 list로 구현

: 노드가 1개 남을 때 까지 재귀

: K 번째로 이동 -> 삭제 -> ( list.end()인 경우 처음으로 옮기기 ) -> 재귀

● 주의 할 것

: K 번째 이지만 이동 횟수는 K-1 임

: 삭제한 다음 iterator가 list.end()를 가리킬 수 있음

● 참고 할 것

: NULL

● 풀이 코드

#include using namespace std; // 삭제 작업이 많기에 list로 구현 list l; list::iterator it; int N, K; void josephus() { // 노드가 1개 남으면 출력하고 종료 if(l.size() == 1) { cout << l.front(); return ; } // k번째 이므로 k-1번 이동 for(int k = 0; k < K - 1; k++) { // 이동 후 마지막인 경우 처음으로 옮기기 it++; if(it == l.end()) it = l.begin(); } // 출력 후 삭제 작업 cout << *it << ", "; it = l.erase(it); // 삭제 한 다음 노드가 끝인 경우 처음으로 옮기기 if(it == l.end()) it = l.begin(); // 재귀 함수 josephus(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; // 리스트 초기화 작업 for(int n = 1; n <= N; n++) l.push_back(n); // iterator 초기 설정 it = l.begin(); // 출력 cout << "<"; josephus(); cout << ">"; return 0; }

● [백준] - [알고리즘 기초 1/2] - [200 - 자료구조 1] 문제집

번호 문제 번호 문제 이름 풀이 링크 1 10828 스택 https://pirateturtle.tistory.com/153 2 9093 단어 뒤집기 https://pirateturtle.tistory.com/154 3 9012 괄호 https://pirateturtle.tistory.com/155 4 1874 스택 수열 https://pirateturtle.tistory.com/156 5 1406 에디터 https://pirateturtle.tistory.com/158 6 10845 큐 https://pirateturtle.tistory.com/161 7 1158 요세푸스 문제 https://pirateturtle.tistory.com/162 8 10866 덱 https://pirateturtle.tistory.com/164

from http://pirateturtle.tistory.com/162 by ccl(A) rewrite - 2021-07-27 00:00:24