[1021]. 회전하는 큐

[1. 문제설명]

연산1: 첫번째 원소를 제거한다.

연산2: 첫번째 원소를 왼쪽으로 한칸 이동

연산3: 마지막 원소를 오른쪽으로 한칸 이동

 

큐에 처음 포함되어 있던 수가 N 개,

뽑고자 하는 원소의 위치가 입력으로 주어 질 때,

원소를 주어진 순서대로 뽑아내는데 필요 한,

2번, 3번 연산의 최소 값을 출력

 

 

[2. 풀이 접근]

1. 완전 탐색
   => deque 에 첫번째 원소가 찾고자 하는 원소인 경우, 연산 1 수행 후, 다음 재귀 호출
   => 위 경우가 아닌 경우, 연산 2 수행 후 기존 deque 복원 후, 연산 3 수행
   ==> 문제점, 무한 루프 발생
   ==
   ==> 2번 연산 수행 후 재귀 호출 시 연산 3을 수행 할 경우, 원래 상태로 복원 되버림
   ==> 일종의 cycle 이 발생 함.
2. 완전 탐색 Cycle 수정 버전
   => 연산 1을 수행 할 수 없을 경우, 현재 연산에 근거하여 다음 연산을 선택
   => 연산 1 또는 연산 2 인 경우 연산 2 수행 후 재귀 호출의 결과를 a+=1 에 저장
   => 연산 1 또는 연산 3 인 경우 연산 3 수행 후 재귀 호출의 결과를 b+=1 에 저장
   => a 와 b 의 최소값을 선택 후 반환
   ==> 문제점, 예제 입력 중 답이 8인 케이스에서 최소 값이 2를 넘기는 경우가 없었음.
   ==
   ==> 연산 수행 여부와 상관 없이 a 와 b 가 모두 0으로 선 초기화 후 결과를 업데이트 함.
   ==> 연산 2 수행 후 연산 3은 수행 할 수 없으므로, 이 경우 b 는 무조건 0 
   ==> 따라서 최소 값이 0 으로 반환 되는 경우가 많음
3. 2번 완전탐색 에서 최소값 수정 버전
   => 각 연산을 수행 하기 전, a 와 b는 모두 math,MaxInt 로 초기화
   => 실제 연산 이 수행했을 때만 a 또는 b 를 0으로 초기화 후, 결과를 설정
   ==> 문제점, timeout
   ==> 전수조사 방식으로는 시간 내 풀이 불가
   ==> 작성해야함................ 

 

 

완전탐색 풀이 시,

- 2번 연산

   |- 3번 연산

 

은 사이클이 되버리므로, 무한루프를 유발함

 

 

분기 에 따른 값 

최소, 혹은 최대 값 선별 시

주의할 점