공주구하기

Question

공주구하기 문제에 대해 질문있습니다. 저는 강사님과 조금 다르게 풀었습니다. input_list에 들어있는 요소의 개수가 k보다 작을 때, k가 짝수라면 input_list[1]이 답이 되고 k가 홀수라면 input_list[-1]이 답이 되는 규칙을 찾았습니다. 임의의 예시를 만들어 해당 규칙을 적용시켜보니, 모든 사례에 이 규칙이 성립하는 것을 발견하였습니다. 해당 규칙을 토대로 알고리즘을 작성하여 채점기를 돌려보았는데,  in3.txt에 대해서만 wrong answer를 유발합니다. 제가 찾은 규칙이 잘못된 것인지, 아니면 코드의 다른 부분에 문제가 있는지 궁금합니다. 자세한 답변 부탁드립니다. 감사합니다. import  sys sys.stdin  =   open ( r " C: \U sers \m y\Desktop\Documents \파 이썬 알고리즘 문제풀이 ( 코딩테스트 대비 ) \섹 션 5 \5 . 공주구하기 \i n3.txt " ) n, k  =   list ( map ( int , input () .split ())) input_list  =   list ( range ( 1 , n  +   1 )) def   save_princess ( input_list ,  k ):           while   True :                   if   len ( input_list )   >=  k:                           input_list.pop ( k - 1 )              for  i  in   range ( k - 1 ) :                                   input_list.append ( input_list.pop ( 0 ))                       else :                           if  k  %   2   ==   0 :                                  result  =  input_list [ 1 ]                  print (result)                  break                           else :                                  result  =  input_list [- 1 ]                  print (result)                  break              save_princess ( input_list, k )

banggoo1152 · Answer

답변 감사합니다. 제가 잘못된 규칙을 찾았었네요. 그리고 큐의 끝에 있는 요소를 pop하지 않고, 중간에 위치한 요소를 pop 했었네요. 스택 또는 큐를 구현할 때, 해당 자료구조의 끝에 위치한 요소를 pop해야 하는 것이 원칙인게 맞습니까?

김태원 · Answer

안녕하세요^^ input_list에 들어있는 요소의 개수가 k보다 작을 때, k가 짝수라면 input_list[1]이 답이 되고 k가 홀수라면 input_list[-1]이 답이 되는 규칙을 찾았습니다. 위 규칙이 잘못된 것 같습니다. 리스트에 7개가 남았고 k가 8일때 한 번 해보세요. 규칙이 통하지 않습니다.