큐- 요세푸스 문제

1. 문제

/*
문제 : 요세푸스 문제
내용 : 
      - N명 사람이 원 형태로 서 있음
      - 각 사람은 1번부터 N번까지의 번호표 갖고있음
      - 임의 숫자 K 주어질 때 사람을 없앤다 
        -> 1번 기준 시계 방향으로 K 번째 사람 없애기
        -> 없앤 사람 다음 사람 기준으로 다시 K번째 사람 없애기
      - N과 K가 주어졌을 때 마지막에 살아남는 사람 번호 반환하는 soulution함수 구현하기!
조건 : 
    - queue 사용하기
    - N, K 는 1이상 1000이하 자연수
*/

2. 처음 접근 코드

•  못 풀엇음 45분 걸림..

#include <queue>
#include <iostream>
using namespace std;
/*
문제 : 요세푸스 문제
내용 : 
      - N명 사람이 원 형태로 서 있음
      - 각 사람은 1번부터 N번까지의 번호표 갖고있음
      - 임의 숫자 K 주어질 때 사람을 없앤다 
        -> 1번 기준 시계 방향으로 K 번째 사람 없애기
        -> 없앤 사람 다음 사람 기준으로 다시 K번째 사람 없애기
      - N과 K가 주어졌을 때 마지막에 살아남는 사람 번호 반환하는 soulution함수 구현하기!
조건 : 
    - queue 사용하기
    - N, K 는 1이상 1000이하 자연수
*/
int solution(int N, int K) 
{
    int FinalNum = 0;
    queue <int> Q;
       
    if (N == 1) return 1;
    
    // 큐를 1부터 일단 채워준다.
    for (int i = 1; i <= N; i++)
    {
        Q.push(i);
    }
    
    // 1에서 시계방향 기준으로 k번째를 지우기 전에!
    // 그 K번째 애를 front 만들어줘야 함 ->  그럼 그 만큼 pop시켜야함
    while (!(Q.front() == (N-K)))
    {
        Q.push(Q.front());
        Q.pop(); // 근디 팝하기 전에 front인 애 값을 알아야 하니까 걔를 먼저 푸쉬하고 팝해준당        
    }

    // 여기서부턴 front가 1에서부터K번째다 
    Q.pop(); //그리고 데이타가  N-1개임!

    // 여기에서의front+K 번째 애를 계속 pop하면 됨
    while () // 조건 어케 써야할지 모르겠다
    {
        Q.push(Q.front());
        Q.pop();
    }
    
    FinalNum = Q.front();

    return FinalNum;
}

int main()
{

    cout << solution(5, 2) << endl; // 3

    return 0;
}

 

3. 정답 (솔루션함수)

int solution(int N, int K) 
{
    queue <int> Q;       
    
    // 큐를 1부터 일단 채워준다.
    for (int i = 1; i <= N; i++)
    {
        Q.push(i);
    }
    
    while (Q.size() > 1)
    {
        for (int i = 1; i < K; i++)
        {
            Q.push(Q.front());
            Q.pop();
        }
        Q.pop();
    }
  

    return Q.front();
}

 

4. 코멘트

• 역시나 조건을 만드는 게 가장 어렵다.
• pop 함수는 front만 팝하고 반환하는 게 없다는 점을 쓰는 게 어려웠다
  • 그래서 front만 조지니까 pop할 애를 front로 만드는 게 중요했다
• 마지막 1개 남을 때까지 하는 거니까 Q.size()>1 조건을 써야 했었다...