[백준] IF문 좀 대신 써줘 19637번 - (C++ 20, C++ 23)

 

 

간만에 백준 문제를 풀어봤습니다!

보통 난이도를 가리고 편견없이 풀곤하는데,

가볍게 읽어도 문제가 어려워 보이지 않아

c++를 조금 더 공부 해보았습니당. 

https://www.acmicpc.net/problem/19637

 

C++20/23의 단순한 활용 경험과,

출력 성능 비교를 포함한 결과를 공유합니다~~!

 

---

문제 분석

문제는 다음과 같은 과정으로 해결했습니다

1. 입력 처리: 전투력 구분 (name, power)와 사용자 전투력(userPower)을 입력받습니다.
2. 이분 탐색: std::lower_bound를 활용하여 각 사용자 전투력에 맞는 전투력 구분을 빠르게 탐색합니다.
3. 출력: 각 사용자 전투력에 해당하는 전투력 이름을 출력합니다.

---

핵심 풀이 : 이분 탐색

 

입력의 밑줄 내용을 보면 알 수 있는 점이 있습니다.

 

1) 입력값은 정렬되어 있다.

2) 여러 개인 경우는 먼저 입력된 하나만 출력한다.

 

1)의 조건이 없다면 입력을 받은 값의 순서를 모두 기록했어야 할 것입니당.

하지만 우리의 값은 정렬되어 있기에 2)의 조건이 무시할 수 있는 조건이 되게 됩니다.

또한 정렬된 값이라면 굳이 순차 탐색을 하지 않고, 이분 탐색을 하는 것이 유리하게 됩니다.

 

---

 

std::lower_bound

 

std::lower_bound - cppreference.com

 

std::lower_bound는 이분 탐색을 기반으로 하며, 정렬된 범위에서 주어진 값보다 크거나 같은 첫 번째 위치를 반환합니다. 그렇기에 이번 탐색에서 가장 적합한 대상으로 볼 수 있습니다.

auto it = lower_bound(cp.begin(), cp.end(), userPower, [](const CombatPower& c, int p) {
    return c.power < p;
});

• cp.begin()에서 cp.end()까지 탐색하며, userPower보다 크거나 같은 값을 찾습니다.
• 람다 함수로 비교 기준을 정의했습니다.

 

---

 

코드 분석 및 구현

1. 구조체 정의 및 기본 설정

: 전투력 구분을 저장할 구조체와 관련 변수들을 선언합니다.

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <ranges>
#include <print>

using namespace std;

// 전투력 저장
struct CombatPower {
    string name;
    int power;
};

// 입력 N, M
int N, M;

// 모든 전투력
vector<CombatPower> cp;

 

2. 이분 탐색 함수 구현

std::lower_bound를 활용해 사용자 전투력에 맞는 전투력 구분을 찾습니다.

string findCombatPower(int userPower) {
    auto it = lower_bound(cp.begin(), cp.end(), userPower, [](const CombatPower& c, int p) {
        return c.power < p;
    });
    return it->name;
}

 

3. 입력 처리 및 결과 출력

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    cp.reserve(N);
	
    // N 개의 기준 전투력 입력 
    for (int i : views::iota(0, N)) {
        string name;
        int power;
        cin >> name >> power;
        cp.emplace_back(name, power);
    }
    
    // M 개의 전투력에 대한 측정
    for (int i : views::iota(0, M)) {
        int userPower;
        cin >> userPower;
        println("{}", findCombatPower(userPower));
    }

    return 0;
}

std::ranges::views::iota

std::ranges::views::iota는 C++20부터 도입된 것으로, 범위 기반 반복을 생성합니다.

• 기존의 for (int i = 0; i < N; ++i)를 대체합니당
• views::iota(0, N)은 [0, 1, 2, ..., N-1]의 범위를 만듭니다.

std::ranges::views::iota, std::ranges::iota_view - cppreference.com

 

---

전체 코드

위의 내용을 하나로 통합하면 전체 코드는 다음과 같습니다.

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <ranges>
#include <print>

using namespace std;

struct CombatPower {
    string name;
    int power;
};

int N, M;
vector<CombatPower> cp;

string findCombatPower(int userPower) {
    auto it = lower_bound(cp.begin(), cp.end(), userPower, [](const CombatPower& c, int p) {
        return c.power < p;
    });
    return it->name;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    cp.reserve(N);

    for (int i : views::iota(0, N)) {
        string name;
        int power;
        cin >> name >> power;
        cp.emplace_back(name, power);
    }

    for (int i : views::iota(0, M)) {
        int userPower;
        cin >> userPower;
        println("{}", findCombatPower(userPower));
    }

    return 0;
}

 

 

---

 

C++23 print 활용

- std::print

• 기존의 std::cout 대신 std::println을 사용하여  cout << ~ << '\n'; 의 구조 탈출 가능!
• std::println은 Python 스타일의 문자열 포매팅을 제공!

// 기존 코드
cout << findCombatPower(userPower) << '\n';
// println 이용
println("{}", findCombatPower(userPower));

 

 

아무래도 둘의 성능 차이는 크게 존재하지 않겠지만 출력 코드만 달리하여 제출해보았다.

 

 

눈부신 시간차는 보이지 않기에 한 번 테스트로 짜보고 시간을 측정 해보았다.

cout + endl, cout + '\n', println에 대해 100,000 번 출력에 대해 간단히 성능을 측정해보았다. 

#include <iostream>
#include <chrono>
#include <functional>
#include <print>

double measurePerformance(const std::function<void()>& func, int iterations) {
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < iterations; ++i) {
        func();
    }
    std::cout.flush();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double>(end - start).count();
}

int main() {
    const int iterations = 100000;

    double cout_endl_time = measurePerformance([]() {
        std::cout << "" << std::endl;
        }, iterations);

    double cout_n_time = measurePerformance([]() {
        std::cout << "" << '\n';
        }, iterations);

    double println_time = measurePerformance([]() {
        std::println("");
        }, iterations);

    std::cout << "Performance Results:\n";
    std::cout << "1. std::cout with std::endl: " << cout_endl_time << " seconds\n";
    std::cout << "2. std::cout with '\\n': " << cout_n_time << " seconds\n";
    std::cout << "3. std::println: " << println_time << " seconds\n";

    return 0;
}

 

 

정말 굉장한 성능 차이는 존재하지 않았기에

극한의 시간 효율을 위한 것이 아니라면 큰 영향이 없을 것으로 보인다.

 

잼미따 히히

std::println - cppreference.com