음악취향 timer 1s memory 1024MB

정올 뮤직은 사용자와 취향이 비슷한 유저들의 데이터를 토대로 음악을 추천해주는 어플이다.

해당 어플에서는 취향이 비슷한 유저를 찾기 위해 취향의 유사도를 계산하여 사용한다.

유사도란 취향 순위가 반전되는 쌍의 개수로 정의된다.

유사도를 계산하는 방법은 아래와 같다.

• N개의 노래를 유저 A가 순위를 매긴 순서대로 정렬한다.

• 유저 B가 각 N개의 노래의 취향 순위를 B_1, B_2, ...\, B_N로 매긴다.

• 두 유저의 등수가 반전되는 개수를 찾는다.

  • 노래_i와 노래_j가 반전된다는 것은 i < j 이며 B_i > B_j인 경우를 의미한다.

예를 들어 유저 A가 5개의 노래에 대해 [1, 2, 3, 4, 5]로 각각 순위를 매겼고

유저 B가 같은 순서의 노래들에 대해 [1, 3, 4, 2, 5]로 각각 순위를 매겼다면,

(3 - 2), (4 - 2)와 같은 두 개의 반전되는 순위 쌍이 존재하여, 유사도가 2가 된다.

유저 A가 각 N개의 노래에 대해 1등, 2등, ..., N등으로 순서대로 취향 순위를 매기고,

유저 B가 같은 순서의 노래들에 대해 각각 B_1, B_2, ...\, B_N등을 매겼을 때의 유사도를 출력하는 프로그램을 작성하시오.