글 읽기 - (WA, 벡터 중복제거 방식)

cubic 4년 전 0

두 명단(v1, v2)을 합친 뒤 중복되지 않는 원소를 제거하는 방식을 택했는데요

혹시나 각각의 명단마다 중복된 사람이 있을까봐 각각의 명단에도 중복 제거를 해준뒤 합쳐줬습니다.

알고리즘에 어떤 문제가 있는 걸까요??

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<string> v1, v2;

int main()
{
    cin >> N >> M;

    for (int i=0; i<N; i++)
    {
        string name;
        cin >> name;

        v1.push_back(name);
    }   // 듣도 못한 입력

    for (int i=0; i<M; i++)
    {
        string name;
        cin >> name;

        v2.push_back(name);
    }   // 보도 못한 입력

    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());   // v1 중복 제거

    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());   // v2 중복 제거

    v1.insert(v1.end(), v2.begin(), v2.end());      // v1에 v2 합칙기

    sort(v1.begin(), v1.end());
    v1.erase(v1.begin(), unique(v1.begin(), v1.end()));     // 중복되지 않는 것 제거
    sort(v1.begin(), v1.end());        // 재정렬

    cout << v1.size() << endl;
    for (string name : v1)
        cout << name << '\n';

    return 0;
}

windflower 4년 전 0

http://www.cplusplus.com/reference/algorithm/unique/?kw=unique

unique함수에 대한 레퍼런스 사이트입니다. 39번째 줄이 보장되지 않습니다.

+ 같은 맥락으로 예제를 돌리면 쓰레기값이 출력되는 것을 볼 수 있습니다. https://www.acmicpc.net/board/view/32737를 확인하고 질문을 올려주세요.

cubic 4년 전 0

답변 감사합니다.

unique 사용 시 벡터의 중복된 값이 제거되기 때문에 erase 함수의 매개변수로써 적합하지 않다는 것을 말씀하시고 싶으신건지 모르겠는데

실제로 사용하면 값이 제거되는 것은 아니며 뒤로 밀려나가는 것이고,

함수의 반환값이 중복요소들의 첫번째 위치의 이터레이터어서 erase의 매개변수로써 들어갈 수 있다고 알고 있습니다.

틀린 내용이 있으면 알려주시길 바랍니다.

또한 예제를 돌려서 제대로 나오는 것을 확인했으나 WA를 받아서 질문을 올린것입니다.

질문을 올리기 위해서 반드시 읽어야하는 글이기에 진작에 정독했으나 확인하고 질문 올려달라고 하시다니 마치 그냥 건너뛰었다는 것 마냥 들리니 기분이 조금 언짢네요.

windflower 4년 전 0

1. unique함수의 경우 중복되지 않는 원소의 경우 뒤로 밀려나서 보존되는 것이 아닙니다. 따라서 위 코드에서는 쓰레기값이 남게 되구요. 이를 확인하시라고 레퍼런스 사이트를 올려드렸습니다.

2. 예제가 제대로 출력되지 않습니다. https://ideone.com/R4oGi7 제 로컬 환경 뿐만 아니라 ideone에서도 마찬가지구요.

windflower 4년 전 0

+ 충분하지 못한 답변으로 언짢으셨다면 죄송합니다. 하지만 저는 예제가 돌아가지 않는 코드를 보고서 건너뛰었다고 판단할 수 밖에 없었습니다. (작성자님 로컬에서만 돌아가는 코드도 마찬가지입니다.)

마냥 언짢아하지 마시고 아무런 보상 없이 불평만을 들으며 답을 다는 제 기분도 고려해 주셨으면 좋겠습니다.

cubic 4년 전 0

답변 감사합니다.

아무래도 함수의 작동방식에 대해 잘못 이해하고 있었나보네요.

예제가 제대로 출력되지 않으시다 하여 행여 제 컴파일러에서만 나오는 것인가 염려하여 해시코드 사이트의 온라인 컴파일러를 사용했으나

똑같은 결과를 받았습니다. 앞으로는 답변자님께서 제공해주신 사이트를 사용해야 할 것 같습니다.

감사합니다. 알고리즘을 새로 생각해봐야겠네요.

cubic 4년 전 0

노고에 수고가 많으십니다.

실력을 키워서 답변 하는 데에 도움이 되도록 해보겠습니다.

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

문제

문제

출처

ICPC

(WA, 벡터 중복제거 방식)

cubic 4년 전 0

windflower 4년 전 0

cubic 4년 전 0

windflower 4년 전 0

windflower 4년 전 0

cubic 4년 전 0

cubic 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말