파이썬 코딩테스트 스터디 4주차 #2 - 요세푸스 문제

N명의 사람이 원 형태로 서있다.

각 사람은 1부터 N까지 번호표를 갖고 있다.

그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 제거

 

1. 1번 번호표를 가진 사람을 기준으로 K번째 사람 제거
2. 없앤 사람 다음 사람 기준으로 다시 K번째 사람 제거

 

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

- 제약 조건

• N과 K는 1이상 1000이하의 자연수

 입출력 예 

N	K	return
5	2	3

 

 

 

그림 설명이 아주 자세히 되어있다.

 

코딩 테스트 합격자 되기 : 파이썬편 - 191page

 

 

■ 리스트로 설명

5

4

3

2

1

이렇게 데이터가 있을 경우,

 

 

step 1 . 제일우측부터 k-1번째 데이터까지. 여기선 k가 2이므로 k-1 = 1

             즉 1을 제일 pop하고, 다시 제일 좌측에 push

1

5

4

3

2

 

 

step 2. 그리고 제일 우측의 데이터를 pop 여기선 2가 pop됨.

1

5

4

3

 

1

5

4

3

 

 

그리고 다시 step1~2시작

k가 2이므로 ,  k-1 = 1 까지의 데이터 pop&push

  

3

1

5

4

 

그리고 pop. 여기선 4가 pop됨.

3

1

5

 

3

1

5

 

이런식으로 하면 

마지막으로 3이 남음 .

return 3

 

 

 

교재 192page에 나온 예시는  K = 3인 경우이나 

이 부분 설명이 빠져있다.

 

■ 문제 분석하기

1. 첫 번째 데이터부터 마지막 데이터까지 queue에 push
2. 큐에서 k-1번째까지의 데이터를 각각 front에서 pop하고 rear에 push
3. k번째 데이터를 팝하고 출력 
4. 과정 2~3을 queue에 원소가 없을 때까지 반복

 

다시 한번, K가 3인 경우다. N=5, K=3

코딩 테스트 합격자 되기 : 파이썬 편 192page

 

코딩 테스트 합격자 되기 : 파이썬 편 193page

 

 

■ 소스 코드

from collections import deque

def solution(N,K):
	#1부터 N까지 번호 deque에 추가
    queue = deque(range(1,N+1))
    while(len(queue)>1):   #deque에 원소가 1개 남을 때까지 반복
    	for _ in range(K-1) :	# K-1까지 pop  &  push
		    queue.append(queue.popleft())	#그림이랑 반대로 소스에서는 왼쪽에서 빼서 오른쪽으로삽입
    	queue.popleft()	# k번째 원소 제거
    
    return queue[0]

 

 

♬ 자료 출처 - 책

코딩 테스트 합격자 되기 - 파이썬 편

 

 

 

이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 

감사합니다.