강의로 돌아가기
HongSoonYeop

[코드있음] 왜 틀렸는지 전혀 모르겠습니다.

정렬 시킨 A에 대해 A보다 큰 수중 가장 작은걸 삭제하는 식으로 했는데 왜 틀리는지 모르겠습니다.

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = -1;
    set<int> b;
    for(int i=0;i<B.size();i++)
    {
        b.insert(B[i]);
    }
    answer = 0;
    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());
    //auto fs = b.begin();
    for(auto u : A)
    {
        //cout << u <<"\n";
        auto it = b.upper_bound(u);

        if(it!=b.end())
        {
            answer++;
            b.erase(it);
        }


    }
    return answer;
}
  • HongSoonYeop

    정확성은 다 맞고 효율성1,2, 번만 틀립니다

    HongSoonYeop―Sep 28, 2022 16:11
  • Horrorkist

    upper_bound는 수행시간이 O(logN)이고 그걸 N번 수행하니 이 풀이의 수행시간은 O(NlogN)입니다. O(N) 안에 해결할 수 있는 방법을 생각해보세요

    Horrorkist―Sep 29, 2022 00:16
  • HongSoonYeop

    시간초과가 아니라 틀리다고 나옵니다.

    HongSoonYeop―Oct 04, 2022 20:57
0 개의 답변
답변 쓰기
This input form supports markdown syntax. Please refer to 마크다운 가이드.