• 발상:★★★, 구현:★★★
• IPSC에서 만든 언어인 Quack를 쓰는 문제
• 기본적인 발상은 다음과 같다. 계속 dequeue 와 enqueue를 반복하면서 복사할 i번째 원소가 나오면 레지스터에 저장했다가, 붙일 위치가 나오면 붙이고, 다시 복사할 i+1번째 원소가 나오면 레지스터에 저장했다가.. 이런식으로 반복하는 것이다. 이렇게 하면 대충 O(n^2)의 알고리즘이 나오게 된다.
• 이제 구현 디테일이 문제인데.. 처음에는 3종류의 특수값(!,#,@ 으로 표기) 을 이용해서 작업을 처리하려고 생각했다.
  • 1) 1,2,3,4 가 입력으로 들어온다면, 처음에 전처리 단계에서 !1!2!3!4#@ 과 같이 바꿔준다
  • 2) !가 나올때까지 큐를 로테이트 시킨다
  • 3) !뒤에 숫자를 레지스터에 저장하고, 역시 로테이트 시킨다. !2!3!4#@1 (1) 인 상태이다. (괄호 안은 레지스터에 저장된값)
  • 3-1) 만약 다음 값이 #이라면 7)로 이동
  • 4) @이 나올때까지 로테이트 ⇒ @1!2!3!4# (1)
  • 5) 레지스터에 있는 값을 뒤에 붙인다 ⇒ @1!2!3!4#1 (1)
  • 6) 2~5를 반복
    • 두번째 루프에서는 다음 과정을 거친다

      • !2!3!4#1@1
        !3!4#1@12 (2)
        @12!3!4#1 (2)
        12!3!4#12@ (2)

  • 7) 여기에 왔다는 것은, 마지막으로 레지스터에 있는 값을 붙이고 종료하면 된다는 의미이다. #123@1234 (4) 이런 상태이다
  • 8) @이 나올때까지 로테이트 시킨다 @1234123
  • 9) 레지스터에 있는 값을 붙이면 끝
• 입력값과 겹치지 않는 3개의 특수값이 필요한데.. 이것을 찾을 방법이 없어서 그냥 적당히 숫자 3개를 골라서 특수값으로 사용했다. 총 범위가 65535이고. 입력값은 최대 400개니까 설마 겹치겠어 하는 생각으로 54321,54322,54323 같으 식으로 세개를 정했다
• 문제가 된 부분은 연산횟수. 대략 10*n^2 번의 연산이 필요했는데, 이말대로라면 n=400일경우 대략 1,600,000 번의 연산이 필요해서 100,000 인 제한횟수를 훌쩍 뛰어넘는다.
• 이부분을 줄이는 것은 매 루프에서 값 한개를 레지스터에 저장했다가 복사하는 것이 아니라, 여러개의 값을 여러개의 레지스터에 저장했다가 붙이는 식으로 처리했다. 레지스터 갯수에 반비례해서 연산량이 줄었고, 레지스터를 20개 사용하면 (코드를 복붙하느라 힘들었다) n=400일때도 80,000번 정도의 연산으로 처리가 가능하다
• 하지만, 이걸 제출하자 30%정도에서 터졌다. 특수값이 겹친것이 맞는것 같았다. 특수값을 바꿔서 제출하자 15%정도에서 터졌거든; 설마 저게 겹치겠어 했는데, 테케가 엄청 많아서 다 잡아내는것 같았다..
• 결국은 유일하게 겹치지 않는게 보장되는 숫자 '0' 만으로 저 세개의 특수값의 역할을 다 하도록 해야 했다.
• 처음에 !를 매 숫자 앞에 붙여주지 않아도 처리 가능하다는 것을 깨닳았고, 결국은 복제할 값의 위치, 붙일 위치, 종료할 위치 이렇게 세군데만 마킹해둘수 있으면 로직을 돌릴수 있다는 것을 알았다.
• 최종 로직은 아래처럼 돌아간다 (!가 실제로는 0이다). 레지스터를 2개 사용했을때의 예시이다

!12345!!
345!!12! (>12)
!!12!345
!12!345! 
!12!345!12 (<12)
12!345!12!

!345!12!12
5!12!1234! (>34)
!12!1234!5 
12!1234!5!
!1234!5!12
1234!5!1234!  (<34)

!5!1234!1234
1234!12345 (>5)
!123451234
1234512345 (<5)

(다이아몬드 이상은 코드 생략)