백준 20949번 [효정과 새 모니터](C++) -yes6686- 티스토리

백준 문제 풀이: 20949 (효정과 새 모니터)

---

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

문제 설명:

주어진 좌표 (a, b)의 **거리의 제곱**을 계산한 후, 해당 거리의 제곱을 기준으로 **내림차순 정렬**합니다. 만약 거리가 같다면 **입력 순서**를 기준으로 오름차순 정렬해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> arr[1001]; // 거리의 제곱과 입력 순서 저장

// 정렬 기준 함수
bool compare(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) { // 거리가 같다면 입력 순서 기준 오름차순
        return a.second < b.second;
    }
    return a.first > b.first; // 거리 기준 내림차순
}

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

    int n;
    cin >> n; // 좌표 개수 입력

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b; // 좌표 입력
        arr[i].first = a * a + b * b; // 거리의 제곱
        arr[i].second = i + 1;        // 입력 순서 저장
    }

    // 정렬
    sort(arr, arr + n, compare);

    // 결과 출력
    for (int i = 0; i < n; i++) {
        cout << arr[i].second << '\n'; // 입력 순서 출력
    }

    return 0;
}

---

코드 설명

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

• 거리의 제곱 계산: 각 좌표 (a, b)에 대해 거리의 제곱을 a² + b²로 계산합니다.
• 정렬 기준:
  • 거리의 제곱이 클수록 우선순위가 높습니다 (내림차순).
  • 거리가 같을 경우, 입력 순서를 기준으로 오름차순 정렬합니다.
• 정렬 함수: compare 함수는 조건에 따라 **내림차순 및 입력 순서**를 처리합니다.
• 결과 출력: 정렬된 결과에서 입력 순서만 출력합니다.

시간 복잡도 분석

• 입력 크기를 n이라 할 때, 정렬의 시간 복잡도는 **O(n log n)**입니다.
• 거리의 제곱 계산은 상수 시간에 수행되므로 전체 시간 복잡도는 **O(n log n)**입니다.

---

결과

거리의 제곱 기준으로 내림차순 정렬 후, 입력 순서를 출력합니다.

• 입력 예시:

  5  
  1 1  
  2 2  
  3 3  
  4 4  
  5 5

• 출력 예시:

  5  
  4  
  3  
  2  
  1

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