[python3] 11866 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

 [ 맨 처음 생각한 풀이 ]

 

1부터 입력 받은 N까지 존재하는 리스트의 0번째 원소와 -1번째 원소가 맞닿아 있는 원 모양의 구조를 생각했다.

현재 위치를 저장한후 그 위치를 기준으로 다음 K번째 요소가 어디에 있는지를 계산하면 된다. 

그리고, 특정 위치의 원소를 제거해야 하므로 pop()을 사용하면 되겠다고 생각했다.

 

K번째 요소가 리스트의 크기를 넘어가는 경우, 원 모양의 특성상 0번부터 시작하게 되는데, 이것은 원소의 전체 길이와 현재 위치를 나눈 나머지를 이용해 계산할 수 있다.

 

결과는 <a, b, c, d, ... , f> 식으로 출력되어야 하는데. < a, b, c, d, ..., f > 로 출력했더니 틀렸습니다가 계속 떠서 고생 좀 했다...

겨우 이것 때문에... <  a, b, c, d, ..., f  > ----> "     " 이 부분 때문에 ....ㅋㅋㅋㅋ

 

	from sys import stdin
	N, K = map(int, stdin.readline().split())
	yo = list(i for i in range(1, N+1))
	result = []
	now = 0 #now : 현재 위치를 나타냄
	while len(yo) >1 :
	now += K
	if now > len(yo):
	now = now % len(yo)
	if now ==0:
	now = now + len(yo)
	now -= 1
	result.append(yo.pop(now))
	print("<", end = "")
	for i in range(len(result)):
	print(result[i], end = ", ")
	print(yo.pop(), end = "")
	print(">")

view raw 11866.py hosted with ❤ by GitHub

다른 분들은 Queue를 이용해서 푼 것 같던데, 고백하자면 큐 구조의 사용이 대놓고 문제에 주어지지 않는 한.. 익숙치 않은 것 같다.

음... 파이팅~~!!