백준 9034번 순위

문제

프로 게이머 협회는 등록된 N 명의 선수들에 대한 순위를 유지한다. 선수들의 순위는 게임을 치를 때마다 얻는 점수에 의해 결정된다. 점수를 누적한 값은 랭킹 포인트가 되고, 랭킹 포인트가 높을수록 순위도 높다. 가장 높은 랭킹 포인트를 가진 선수(들)은 순위가 1 이다. 나머지 선수의 순위는 자신보다 한 단계 높은 랭킹 포인트를 가진 선수(들)의 순위에다 해당 선수들의 수를 더한 값이다. 선수들을 1 부터 N 까지의 번호로 구분하자. 예를 들어, N=5 명의 현재 랭킹 포인트가 1 번 선수부터 차례대로 (10, 15, 20, 8, 12) 라고 하면, 선수들의 순위는 차례대로 (4, 2, 1, 5, 3) 이다. 이제 어떤 대회를 통해 일부 선수들이 다음과 같은 점수를 얻었다고 하자. 각 쌍은 (선수 번호, 획득한 점수)이다.

(1, 25), (2, 20), (5, 10)

대회가 종료된 후, 선수들의 기존 랭킹 포인트에 새로 획득한 점수가 더해진 랭킹 포인트는 각각 (35, 35, 20, 8, 22)가 된다. 따라서 선수들의 순위는 이제 (1, 1, 4, 5, 3) 이다.

협회에서는 선수들의 게임 결과를 수시로 발표한다. 발표된 결과를 바탕으로 선수들의 순위 정보를 구하여 어떤 시점에 주어진 선수의 현재 순위를 출력하는 질의를 처리할 수 있는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : fenwick tree

(0) 생각

 k번째 학생의 랭킹은 'k번째 학생의 포인트보다 큰 학생 수' + 1 임을 생각합니다.

(1) 코드 9~19

 각 학생들의 점수를 저장할 struct를 만들어줍니다.

    idx : 입력된 순서

    X   : 학생 번호

    val : idx번째 입력에서 X학생의 총 포인트

(2) 코드 20~22

 좌표 압축을 위해 과정(1)의 struct를 val 순으로 정렬 해주기 위한 기준

(3) 코드 23~25

 좌표 압축 후 다시 입력 순으로 과정(1)의 struct를 정렬 해주기 위한 기준

(4) 코드 70~83

 학생의 최대 포인트는 10^9 입니다. 이를 배열로 잡아줄 수 없겠죠...? (메모리가...)

 질의 M <=2*10^5 이니 점수가 아무리 많아 봤자 2*10^5 일 것입니다.

 따라서 학생들의 좌표를 압축해줍니다. ( 2*10^5 는 충분히 배열로 잡을 수 있죠 )

(5) 코드 85~100

 입력순으로 다시 정렬 후 차례로 탐색합니다.

 'R' 입력일 경우 이전 학생의 점수를 fenwick에서 빼주고, 학생의 새로운 점수를 fenwick에 쌓아줍니다.

 'Q' 입력인 경우 해당 학생보다 큰 포인트를 갖고 있는 학생수 + 1 이 랭킹이 됩니다.

(6) 코드 28~45

 fenwick tree 구현 코드입니다.

 fenwick tree 대신 segtree 써도 똑같이 풀 수 있습니다.

 fenwick tree 가 익숙하지 않으신 분은 백준느님이 써놓으신 좋은 글을 링크해 두겠습니다.

 https://www.acmicpc.net/blog/view/21