발상:★★★, 구현:★★★
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개 사용했을때의 예시이다