[백준] 10867번 : 중복 빼고 정렬하기 - C/C++

 

문제 외에 추가적으로 더 생각해야하는 문제가 아니어서 좋았다.

문제에서 주어진 내용을 따라가면 된다.

 

문제 풀이 순서

1. 수의 개수 N 입력

2. vector에 N개의 수 입력

3. 중복 제거 후 정렬 or 정렬 후 중복 제거

 

N개의 수를 vector에 입력

int n;
vector <int> v;
cin >> n;
    
for(int i = 0; i < n; i++){
   int x;
   cin >> x;
   v.push_back(x);
}

 

벡터에 값을 넣을 때는 크게 두 가지의 방법이 존재한다.

1. 필자처럼 push_back() 사용하기

2. insert() 사용하기

 

언제 어떤 것을 사용할지는 상황에 따라 다르다.

함수	사용 목적	시간 복잡도	특징
push_back()	벡터의 끝에 값을 추가	평균 O(1), 최악 O(n)	동적 배열 확장 시 재할당 발생 가능
insert()	특정 위치에 값을 삽입	평균 O(n)	삽입 위치 이후 원소들이 이동

 

insert()는 원소를 특정 위치에 넣기 때문에

원소들이 이동하는 추가적인 작업이 실행된다.

그렇기 때문에 insert()는 push_back() 함수보다

속도가 느리다는 것이 특징이다.

 

돌아가서 문제를 생각해보자.

문제에서 요구하는 삽입은 insert 보다는 push_back이 더 적합하다.

값을 끼우는 문제는 많이 없는 것 같긴하다.

 

이제 중복되는 값을 처리해주어야한다.

앞서 말한 것 처럼 두 가지 방법이 존재할 것 같긴한데

필자는 정렬 후, 중복 제거 를 택하였다.

다른 방법은 안 해봄

 

정렬은 sort() 를 이용하자.

디폴트로 오름차순 정렬이 되기 때문에

문제에서 요구하는 조건과 딱! 부합한다.

sort(v.begin(), v.end());

 

정렬은 했는데, 중복된 원소를 어떻게 제거할까.

erase 와  unique 를 사용하면 된다.

코드로는 아래와 같이 작성 가능하다.

v.erase(unique(v.begin(), v.end()), v.end());

 

unique는 연속된 중복 원소를 제거하고, 중복되지 않는 요소로 재배열한다.

 

erase는 unique가 반환한 첫번째 원소부터 원래 벡터의 마지막 원소까지를 삭제한다.

erase가 실질적인 벡터 크기를 줄여주는 역할을 하는 것이다.

 

글을 정리하며 느낀 것은

unique가 연속된 중복 원소를 제거하는 것이니까

정렬을 먼저 해주는 것이 맞는 것 같다.

 

 

전체 코드

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

//중복 빼고 정렬하기
using namespace std;

void solve(const vector<int> & v){
    for (int k : v) {
        cout << k << " ";
    }
    cout << endl;
}

int main(){
    int n;
    vector <int> v;
    cin >> n;
    
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    solve(v);

    return 0;
}

 

 

p.s.) solve라는 함수를 새로 만들었습니다.

새로운 함수를 선언한 것에는 여러가지 이유가 존재하죠..

1. 코드의 중복 줄이기

2. 출력 형식 변경 시 ( ) 안에만 변경해도 됨

하지만 간단한 구조에서는 오히려 복잡하게 작용할 수도 있는데요,,

작성한 코드는 간단해보였으나,

int main( ) 함수에서 바로 cout 출력을 해버리니,

syntax 오류가 뜨더라구요.

그래서 새로운 함수를 만드는 방법을 택했습니다.

결과적으로는 오류 없이 답을 맞췄지만 잘 모르겠네요

왜 잘만 출력되던 cout이 제대로 작동하지 않는지는..

 

 

 

 

실버5 난이도의 문제였다.

어떻게 풀어야겠다 라는 생각은 들지만,

사용하는 함수라이브러리는 아직까지 검색해야한다.

이런 점만 고치면 더 성장할 수 있을 것도 같은데

문제 푸는 양만 늘리는 것이 아니라

얼마나 제대로 공부했는지가 중요하겠지만

문제를 안 풀면 어떤 개념이 쓰이는지 알 수 없는 것 아닌가?

조언을 구해보아야겠다.

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️