백준 2517번 달리기

문제 링크입니다: https://www.acmicpc.net/problem/2517

2517번: 달리기

세그먼트 트리와 좌표압축을 활용해야하는 문제였습니다.

각 선수의 실력의 범위는 1 ~ 1,000,000,000 까지이지만 N이 최대 500,000이기 때문에 아래와 같은 알고리즘이 적용 가능합니다.

1. 구조체 벡터를 선언해 ability에는 실력, idx에는 인덱스를 저장해줍니다.

2. 실력 오름차순 정렬을 진행한 뒤, 실력을 [0, N-1) 로 압축해줍니다.

3. 압축을 진행한 벡터에 대해 인덱스 오름차순 정렬을 진행합니다.

4. query 함수를 통해 자신보다 앞서 뛴 주자들 중 자기보다 실력이 안 좋은 선수들의 수를 확인한 뒤 등수를 출력합니다.

5. 등수를 출력한 뒤 현재 주자의 실력을 update 함수를 통해 세그먼트 트리를 업데이트해줍니다.

6. [0, N)까지 4, 5번 반복

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~