HackerRank. New Year Chaos

https://www.hackerrank.com/challenges/one-week-preparation-kit-new-year-chaos/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=preparation-kits&playlist_slugs%5B%5D=one-week-preparation-kit&playlist_slugs%5B%5D=one-week-day-four

New Year Chaos | HackerRank

 

큰 숫자부터 뒤로 밀어주면 된다.

문제는 배열의 최대 크기가 십만이기 때문에, 큰 숫자를 매번 배열에서 찾는다면 시간복잡도가 최대 O(N^2) 가 된다.

따라서 pos[n] = 숫자 n 의 인덱스 를 저장해서 관리한다.

 

그  후 가장 큰 숫자 n 부터 뒤로 밀어주는데 abs(pos[n]-n]) > 2 라면 n 이 최종적으로 위치해야할 위치에서 3 칸 이상 떨어져 있기 때문에 swap 을 세번 이상해야 한다. 따라서 "Too chaotic" 을 출력한다.

 

아니라면 n 을 뒤의 숫자와 swap 해주면 되는데 이때 당연히 pos 도 업데이트 해줘야 한다.

 

 

 

 

 

---

 

나는 pos[] 를 만들고 큰 값 부터 뒤로 미뤘는데,

그냥 배열 q 의 앞에서부터 내 자리가 아니라면 뒤로 무조건 미루면 된다.