[BaekJoon 7568][⚪5] 덩치

❓ 문제

백준 7568 - “덩치”

🎯 난이도

Silver ⚪5

🧠 풀이

1. 내 풀이 (브루트 포스)

- 알고리즘

• Brute Force

- 설명

브루트 포스 방식으로 모든 루프를 돌며 답을 구하는 풀이이다.

다른 더 좋은 풀이가 있나 생각했는데, 모든 루프를 이중으로 돌더라도 '2 ≤ N ≤ 50' 조건에서 'O(N²)'면 기껏해야 '2500번' 루프를 돌게 되므로, '1초'의 시간 제한에서는 매우 널널하다.

따라서 그냥 vector에 입력값들을 모두 저장하고 나중에 브루트 포스 방식으로 이중 반복문을 돌면서 값을 구하도록 구현했다.

브루트 포스 방식으로 이중 반복문을 도므로, 시간 복잡도는 O(N²)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

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

    int iN{};
    cin >> iN;

    vector<pair<int, int>> vecSize{};
    vecSize.reserve(iN);

    while(iN--)
    {
        int iWeight{}, iHeight{};
        cin >> iWeight >> iHeight;

        vecSize.emplace_back(pair<int, int>(iWeight, iHeight));
    }

    // 모든 이중 루프를 돌면서 하나하나 비교해서 등수 출력
    for(const auto& pairCurr : vecSize)
    {
        int iCnt{};

        for(const auto& pairOther : vecSize)
        {
            if(pairCurr.first < pairOther.first &&
                pairCurr.second < pairOther.second)
            {
                ++iCnt;
            }
        }

        cout << iCnt + 1 << ' ';
    }

    return 0;
}

---

💭 후기

이런 문제는 더 좋은 방법이 있는지를 먼저 생각하는 것보다, 시간 제한과 메모리 제한을 보고 브루트 포스 같은 간단한 방법으로 해결될 것 같으면 일단 그대로 구현해 보는게 좋다. 더 좋은 방법이 있는지는 상기한 방법대로 일단 해결하고 난 뒤에 고민해도 늦지 않다.

🔗 참고자료

• 브루트 포스 알고리즘