[코딩 테스트 합격자 되기] 문제 15 요세푸스 문제

문제 설명

N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.

• 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution() 함수를 구현해주세요.

 

제약 조건

• N과 K는 1이상 1000이하의 자연수입니다.

입출력의 예

N	K	return
5	2	3

 

정답

Class Queue{
    items = [];
    front = 0; //앞
    rear = 0; //뒤
    
    push(item){
    	this.items.push(item);
        this.rear++; //뒤로 넣으니까
    }
    
    pop(){
    	return this.items[this.front++]; //앞에서 꺼내온다
    }
    
    size(){
    	return this.rear - this.front;
    }
    
    isEmpty(){
	return this.front === this.rear;
    }
}

solution(n,k){
    //원소를 다 큐에 집어넣는다.
    const queue = new Queue();
    
    for(let i=1; i<=n; i++){
    	queue.push(i);
    }
    
    while(queue.size() > 1){
    	//원소가 하나만 남을때까지 loop
        for(let i=1; i<=k-1; i++){
        	queue.push(queue.pop()); //k-1번 pop한 뒤 다시 push
        }
        
        queue.pop(); //그리고 앞에 온 애를 제거
    }
    
    //다 돌고 하나만 남으면
    return queue.pop(); //마지막 요소 return
}