글 읽기 - STL map 고수님들 필독!!!

vjerksen 7년 전 0

map으로 중복 되었는 지 확인하고 벡터로 옮겨서 정렬 후 출력하는 방식을 사용하는데

'런타임 에러' 가 발생됩니다.

고수님들의 조언 부탁드립니다.

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<climits>
#include<map>
#include<set>
using namespace std;
int K,L;
vector<string> str;
map<string, int> student;
vector<pair<int,string> > v;
int main(){
    cin >> K >> L;
    for(int i=0;i<L;i++){
        string temp = "";
        cin >> temp;
        if(student.count(temp)!=0)    // 이미 map에 존재한다면, 기존의 map에서 지우고 다시 삽입.
            student.erase(temp);
        student.insert({temp,i});
    }    
   
    // map전체를 key 값이 아닌 value의 값으로 정렬하기 위해 vector v를 사용.
    for(auto a = student.begin();a!=student.end();a++){
        v.push_back({a->second,a->first});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<K;i++){
        cout << v[i].second << "\n";
    }
    return 0;
}

kesakiyo 7년 전 1

vector v의 사이즈가 K보다 작을 수 있을것 같네요~

vjerksen 7년 전 0

// to. kesakiyo

감사합니다. 덕분에 런타임에러는 잘 해결했습니다. 근데 이번엔 시간 초과가 나옵니다.

제 생각에는 가장 크게 나오는 L =500,000이라 생각하면,

최대 시간복잡도가 O(L*lg(L))정도가 나와서 문제가 안된다고 생각하는데

혹시 의견 부탁드려도 될까요?

kesakiyo 7년 전 1

음 일단 count랑 erase랑 insert가 불필요하게 겹쳐지네요.

생각해보면 key값이 있으면 key를 erase하고 다시 새로은 {key, value} pair를 넣어주는건

불필요한 작업이라는 것을 알 수 있습니다.

student[temp] = i;

라는것으로 위 세가지 작업을 모두 대체할 수 있기 때문이죠.

이거 고치면 아마 1000ms로 AC받지 않을까 싶네요.

vjerksen 7년 전 1

// to. kesakiyo

해결 되었습니다. 감사합니다. 정말 닉 값 제대로 하시는 것 같네요 :)

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

문제

문제

출처

ICPC

STL map 고수님들 필독!!!

vjerksen 7년 전 0

kesakiyo 7년 전 1

vjerksen 7년 전 0

kesakiyo 7년 전 1

vjerksen 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말