글 읽기 - 12015 BST 사용시 시간초과 뜨는 것에 대해 고수님들의 한마디 부탁드립니다.

bgb10 1년 전 0

저도 이분탐색 풀이를 떠올려서 BST를 사용해서 풀었는데요, 바로 시간초과가 뜹니다.

아마 BST가 느려서 시간초과가 난 것 같은데,

1. 혹시 해당 풀이가 '시간을 제외하고는' 맞는 풀이인지,

2. 똑같이 이분탐색을 사용한 풀이인데 직접 구현한 이분탐색은 되고, set 을 사용한 이분탐색을 하면 안될 때가 있는데,

실전에서는 어느 기준을 두고 둘 중 하나를 선택해야 하는지.

에 대해 조언해주셨으면 합니다. 감사합니다!

#include <bits/stdc++.h>
#include <algorithm>
#include <set>
using namespace std;
#define X first
#define Y second

set<pair<int, int>> BST;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        auto it = lower_bound(BST.begin(), BST.end(), make_pair(x, 0));
        if (it == BST.begin()) {
            BST.insert({x, 1});
        } else {
            it--;
            int dp = (*it).Y + 1;
            ans = max(ans, dp);
            BST.insert({x, dp});
        }
    }
    cout << ans;
    return 0;
}

zenith82114 1년 전 1

아니요, 이 코드는 정답이 아닙니다. 아래에 반례가 있습니다.

7이 들어올 때, 실제로는 [1,2,4,5,7]로 5개짜리를 만들 수 있는데

앞에 있는 (6,2) pair를 보고 (7,3) pair를 만들어 버립니다.

여담으로, lower_bound 함수는 헤더에도 있지만 std::set의 멤버함수 중에도 있습니다.

전자보다 후자가 훨씬 빠르고, 이유는 한 줄로 말하자면 std::set이 random-access iterator가 아니기 때문입니다.

(X) auto it = lower_bound(BST.begin(), BST.end(), make_pair(x, 0));

(O) auto it = BST.lower_bound(make_pair(x, 0));

// in
10
1 8 6 9 2 4 5 7 10 3
// out
4
// ans
6

zenith82114 1년 전 0

(수정) 헤더에도 있지만 -> <algorithm> 헤더에도 있지만

bgb10 1년 전 0

답변 정말 감사합니다. 풀이가 틀린 것도 알았고, lower_bound 를 저렇게 사용하면 안된다는 것도 배웠네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

12015 BST 사용시 시간초과 뜨는 것에 대해 고수님들의 한마디 부탁드립니다.

bgb10 1년 전 0

zenith82114 1년 전 1

zenith82114 1년 전 0

bgb10 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말