BOJ 9034 - 순위

링크: https://www.acmicpc.net/problem/9034

오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ

문제

매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다.

먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.

매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다.

내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다.
이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.

점수가 더해질때마다, 이전의 내 점수 위치를 -1하고 새로 더해진 점수 위치를 +1하여 나중에 카운팅될 수 있도록 업데이트하면 된다.

코드

반응형

저작자표시

• 카카오스토리
• 트위터
• 페이스북

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 3640 - 제독  (0)	2020.05.24
BOJ 15480 - LCA와 쿼리  (0)	2020.05.15
BOJ 9034 - 순위  (0)	2020.05.01
BOJ 1539 - 이진 검색 트리  (4)	2020.04.17
BOJ 18109 - 도깨비불  (0)	2020.04.02
SWEA 2112 - [모의 SW 역량테스트] 보호 필름  (0)	2020.02.26