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

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

문제 분석

  • 제한 시간은 널널한 편이다.(2초)
  • 지난 번에 풀었던 2346번,"풍선 터뜨리기 문제"(https://genius00hwan.tistory.com/58) 가 생각난다.
  • 그 문제와 비슷한 논리로 풀어봐야 겠다.
  • 계획:
    <deque> 자료구조를 사용한다.
    deque가 비어있을 때 까지 아래를 반복한다.
    • deque 맨앞에 있는 값을 맨뒤로 넣어주는 행위를 k-1 번 반복한다.
      (재귀함수안에 반복문을 넣는게 바람직하지는 않겠지만 제한시간이 널널하니까 이렇게 해도 될거 같다.)
    • 맨앞에 있는 값을 출력하고, 삭제한다.
  • 주의사항:
    출력할 때"<.,.,...,.,.>"형식으로 출력한다.
deque<int> people; //요세푸스 순열
int n, first; 

void cycle(int x) {
    int m = x - 1;
    while (m--) { // x - 1 번 반복
        people.push_back(people.front()); 
        people.pop_front(); 
        //맨 앞에 값 빼서 뒤에 추가
    }
    cout << people.front();// 맨 앞에 값(x번째 값) 출력
    people.pop_front();// 맨 앞에 값(x번째 값) 제거
    if (people.empty()) return;//deque가 비면 그만!
    else cout << ", ";//다음 값 있으면 "," 출력
    cycle(x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> first;
    for (int i = 1; i <= n; i++) { //인원수 만큼 1부터 deque에 삽입
        people.push_back(i);
    }

    cout << "<";// 출력 시작전 "<"출력
    cycle(first); // 첫 값은 입력된 값
    cout << ">";// 출력 마치고 ">"출력
    return 0;
}

느낀 점

  • 이 문제를 풀면서 가장 크게 느낀 감정은 뿌듯함이다. 유사한 문제를 풀어본 경험으로 쉽게 문제를 해결했다.
  • 출력할 때"<.,.,...,.,.>"형식으로 출력한다는 점이 좀 고민됐는데 출력할때 쉼표를 같이 출력하면 되겠다는 생각이 들었다.
    하지만 출력할 때마다 쉼표를 같이 출력하게 되면 마지막 값을 출력 할 때도 쉼표를 출력하게 된다.
    그래서 재귀함수를 멈추기 위한 if (people.empty()) 문을 이용해 다음값이 있으면 ","를 출력하게 했다.
    (이 부분이 꼼수인지 묘수인지 모르겠지만 좀더 예쁜 답이 있지 않을까하는 생각이든다...ㅎㅎ)

시간 복잡도

  • 1~n까지에 숫자 deque에 삽입 →O(n)
  • deque 맨앞에 있는 값을 맨뒤로 넣어주는 while문 → O(n)(최악의 경우)
  • 재귀함수 반복 → O(n)
    ➣O(n^2)

'Algorithm > baekjoon' 카테고리의 다른 글

[BOJ 5430] AC  (0) 2022.07.25
[BOJ 13335] 트럭  (0) 2022.07.25
[BOJ 1406] 에디터  (0) 2022.07.25
[BOJ 10799] 쇠막대기  (0) 2022.07.24
[BOJ 2346] 풍선 터뜨리기  (0) 2022.07.20

+ Recent posts