Joonas' Note

Joonas' Note

BOJ 9034 - 순위 본문

알고리즘/문제 풀이

BOJ 9034 - 순위

2020. 5. 1. 17:28 joonas

    링크: 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 1539 - 이진 검색 트리  (4) 2020.04.17
    BOJ 18109 - 도깨비불  (0) 2020.04.02
    SWEA 2112 - [모의 SW 역량테스트] 보호 필름  (0) 2020.02.26
    Comments