정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀감
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 함
정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했음:
왕자들은 나이 순으로 1번부터 N번까지 차례로 번호가 매겨짐
그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉음
그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외침
한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 됨
그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외침
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 가게 됨
예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외되는 경우,
처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고
마지막까지 남게 된 7 번 왕자가 공주를 구하러 가게 됨
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램 작성
첫 줄에 입력으로 자연수 N과 K가 주어짐
입력 예시)
8 3
출력 예시)
7
내가 쓴 코드
from collections import deque
import sys
#sys.stdin = open("input.txt", 'rt')
# N명의 왕자, 외치면 안되는 숫자 K
N, K = map(int, input().split())
# N명의 왕자 dequeue에 넣기
princes = []
for i in range(N):
princes.append(i+1)
call = 1 #부르는 숫자
idx = 0 #인덱스
#왕자가 한명 남을때 까지 반복
while len(princes) > 1:
# K 부른 경우
if call == K:
# K 부른 왕자 아웃
princes.pop(idx)
# 부르는 숫자 다시 1로 초기화
call = 1
#맨 끝 왕자가 빠진 경우: index out of range 발생하니까 주의
if idx == len(princes):
#맨 앞 왕자로 돌아감
idx = 0
#맨 끝 아닌 왕자가 빠진 경우, 그 왕자가 있던 인덱스의 왕자부터 이어서 숫자를
#불러야 하니까 별도의 처리 안해도됨
# K 아직 안된 경우
else:
# 숫자 키우기
call += 1
# 다음 왕자로 넘어가야 하는데 맨 끝 왕자면 처음으로 이동
if idx == len(princes) - 1:
idx = 0
# 맨 끝 왕자 아니면 그냥 옆으로 이동
else:
idx += 1
#마지막 남은 한 명의 왕자 출력
print(princes[0])
모범답안
#모범답안
import sys
from collections import deque
#sys.stdin = open("input.txt",'rt')
n, k = map(int, input().split())
q = list(range(1,n+1))
dq = deque(q)
while dq:
# K 전까지 숫자 부르는 왕자들 뒤로 가서 줄서기
for _ in range(k-1):
cur = dq.popleft()
dq.append(cur)
# K 부른 왕자 아웃
dq.popleft()
#한 명 남으면 그 왕자 셀렉
if len(dq) == 1:
print(dq[0])
#선택된 왕자도 빼줘야 프로그램이 정상적으로 종료됨 (while dq 반복문 이니까)
#break 해도됨
dq.popleft()
느낀점
1. 와..ㅎㅎㅎㅎㅎㅎ 효율성 차이 대박!!!
물론 비효율적일거라고 생각은 했지만 이정도일줄을 몰랐다.
뒤로 가서 다시 줄서는 개념으로 푸는 방법을 생각 못했다. 바부
2. dequeue는 양방향 큐로, 양쪽 끝에서의 삽입과 삭제가 빠른 자료구조임
from collections import deque
dq = deque(lst)로 리스트를 양방향 큐로 전환
스택(append, pop)과 큐(append, popleft)로 모두 사용할 수 있음
양 끝 데이터 처리의 속도가 중요할 때 유용!!
pop(index), popleft(index)는 불가능함: 중간 원소 빼는건 비효율적
3. 반복문 안쓰고 리스트에 숫자 순서대로 넣는 방법도 명심!
numLst = list(range(시작숫자, 끝숫자+1)
4. 모범답안 기반으로 다시 푼 내 코드가 증말.맘에든당ㅎ
다시 풀어보기
#다시
from collections import deque
N, K = map(int,input().split())
princes = list(range(1,N+1))
princes = deque(princes)
while len(princes) > 1:
for _ in range(K-1):
tmp = princes.popleft()
princes.append(tmp)
princes.popleft()
print(princes[0])