파이썬 백준 알고리즘 - 등수 구하기 풀이 해석

안녕하세요! 알고리즘 열정 넘치는 개발자 여러분, 반갑습니다. 오늘은 "등수 구하기" 문제를 다뤄보려고 합니다. 이 문제는 주어진 점수 리스트에서 새로운 점수의 등수를 찾는 문제입니다. 풀이 방법과 코드를 통해 자세히 알아보겠습니다. 그럼 시작해봅시다!

문제 내용

주어진 점수 리스트에서 새로운 점수의 등수를 구해야 합니다. 등수는 동점자가 있을 경우 이전 등수보다 낮은 등수로 책정됩니다.

문제 이해하기

주어진 입력은 세 개의 값으로 이루어져 있습니다. 첫 번째 값인 **N**은 현재 점수 리스트의 개수입니다. 두 번째 값인 **new**는 새로운 점수입니다. 세 번째 값인 **P**는 등수를 찾을 대상이 되는 새로운 점수의 인덱스입니다.

풀이를 위해 현재 점수 리스트를 입력받고, 새로운 점수를 기존 리스트에 추가합니다. 그리고 새로운 점수를 기준으로 정렬된 리스트를 생성합니다. 등수를 찾을 대상인 새로운 점수가 리스트에 존재하는지 확인한 후, 존재한다면 등수를 출력합니다. 존재하지 않는다면 -1을 출력합니다.

풀이 코드

pythonCopy code
N, new, P = map(int, input().split())

if N > 0:
    score_list = list(map(int, input().split()))
else:
    score_list = list()

new_score_list = [(v, i) for i, v in enumerate(score_list)]
input_ = (new, len(new_score_list))
new_score_list.append(input_)

sorted_new_score_list = sorted(new_score_list, key=lambda x: (x[0], -x[1]), reverse=True)
pruned_new_score = sorted_new_score_list[:P]

if input_ in pruned_new_score:
    for i, v in enumerate(pruned_new_score):
        if v[0] == new:
            print(i + 1)
            break
else:
    print(-1)

풀이 방법

해당 문제를 해결하기 위해 다음과 같은 풀이 방법을 사용합니다.

1. 입력 값으로 현재 점수 리스트의 개수 N, 새로운 점수 new, 등수를 찾을 대상의 인덱스 **P**를 받습니다.
2. 만약 **N**이 0보다 크다면, 현재 점수 리스트를 입력받습니다.
3. 현재 점수 리스트를 이용하여 (점수, 인덱스) 형태의 리스트인 **new_score_list**를 생성합니다.
4. 새로운 점수 **new**와 **new_score_list**의 길이를 이용하여 (new, 길이) 형태의 튜플인 **input_**를 생성하고, **new_score_list**에 추가합니다.
5. **new_score_list**를 점수를 기준으로 내림차순으로 정렬하고, 점수가 동일한 경우 인덱스를 내림차순으로 정렬합니다.
6. 정렬된 **new_score_list**에서 상위 **P**개의 요소를 추출하여 **pruned_new_score**로 저장합니다.
7. **input_**가 **pruned_new_score**에 존재하는지 확인합니다.
8. **input_**가 존재한다면, **pruned_new_score**에서 **new**와 동일한 점수를 찾고, 등수를 출력합니다.
9. **input_**가 존재하지 않는다면, -1을 출력합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(NlogN)입니다. 점수 리스트를 정렬하는 과정에서 O(NlogN)의 시간이 소요됩니다. 그 후, **pruned_new_score**에서 **input_**의 존재 여부를 확인하는 과정은 O(P)입니다. 따라서, 전체적으로 O(NlogN)의 실행 시간이 소요됩니다.

 

아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요!

 

👉 백준 알고리즘 모음