백준 1205번 [등수 구하기](C++) -yes6686- 티스토리

백준 문제 풀이: 1205 [등수 구하기]

---

문제 링크: https://www.acmicpc.net/problem/1205

문제 설명:

새로운 점수 s가 주어졌을 때, 이 점수를 주어진 점수 리스트에 추가했을 때의 등수를 구하는 문제입니다. 단, 등수는 1위부터 시작하며 점수가 높은 순으로 매겨지고, 리스트의 길이는 최대 p개까지만 유지됩니다. 만약 s가 추가될 수 없다면 -1을 출력합니다.

---

문제 해결 코드

// 백준 1205 - 등수 구하기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, s, p;
    cin >> n >> s >> p;

    vector scores;
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        scores.push_back(score);
    }

    // 새로운 점수를 리스트에 추가
    scores.push_back(s);

    // 점수 리스트 내림차순 정렬
    sort(scores.rbegin(), scores.rend());

    // 새로운 점수의 등수를 계산
    int rank = 1;
    for (int i = 0; i < scores.size(); i++) {
        if (i > 0 && scores[i] < scores[i - 1]) {
            rank = i + 1; // 중복 점수 고려하여 순위 갱신
        }
        if (scores[i] == s) {
            // 리스트 크기가 제한을 초과하고 점수가 리스트 마지막보다 낮으면 -1 출력
            if (i >= p) {
                cout << -1 << '\n';
                return 0;
            }
            cout << rank << '\n';
            return 0;
        }
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 점수 리스트에 새로운 점수를 추가하고 내림차순 정렬합니다.
  • 등수를 계산하며 리스트의 길이가 p를 초과하면 불가능(-1)을 출력합니다.
• 구현 세부사항:
  • 점수 리스트 정렬 시 sort(scores.rbegin(), scores.rend())를 사용하여 내림차순으로 정렬합니다.
  • 중복 점수를 고려하여 동일 점수는 같은 등수로 처리합니다.
• 시간 복잡도 분석:
  • 정렬: O(n log n)
  • 등수 계산: O(n)
  • 총 시간 복잡도: O(n log n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!