Hackerrank - New Year Chaos

https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

New Year Chaos | HackerRank

이번에 풀어본 문제입니다.

문제) 사람들이 일렬로 물건을 사기 위해 줄을 서있습니다. 이 때, 모든 사람들은 앞 사람들에게 돈을 주고 자리를 바꿀 수 있고, 특정 사람이 다른 사람을 매수할 수 있는 최대 횟수는 2회입니다.(즉, 자신의 자리보다 최대한 2칸까지 앞으로 갈 수 있습니다.) 숫자들의 List가 주어질 때, 매수가 일어난 최소 횟수를 구하시오.

 

[예시]

 

초기 상태 : [1, 2, 3, 4, 5]

최종 상태 : [2, 1, 5, 3, 4]

* 엄청나게 큰 Input이 테스트 항목에 있으므로, 단순히 풀기만 해서는 안됩니다.(여기서 많은 시간을 보냈습니다. 사실 답을 찾지 못해서 discussion에 들어가서 힌트를 얻었습니다 ㅠㅠ)

 

1. 방법

* (매수가 일어난 총 횟수) = (각각의 사람들이 매수당한 횟수의 총 합)

  -> 각 사람들이 매수당한 횟수는 특정 사람(x)보다 앞에 있지만 뒷번호를 가진 사람(y: y>x)을 찾으면 됩니다.

  -> 특정 사람의 순서(x)보다 뒷 번호를 가진 사람(y : y>x)은, 특정 사람의 원래 자리(x) 보다 1자리 앞(x-1)까지 갈 수 있습니다.(y : y≥x-1)

     (이 부분을 이해하는 것이 중요합니다. 뒤에 있던 사람이 매수를 하면 뒤에 있던 사람은 자리 (x)로 오게 됩니다.)

  -> 즉, 원래 특정 사람이 x에 위치해 있었고 현재 위치가 i라면, x-1부터 i-1까지 위치에 x보다 큰 숫자가 몇개 있는지 찾으면 됩니다.

 

코드는 매우 간단하므로 생략하겠습니다. -!