[백준] 1181번 단어정렬 (C++) - sort, compare

문제

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

코드

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

using namespace std;

bool compare(string a, string b){
  if(a.length() == b.length()){
    return a < b;
  }
  return a.length() < b.length();
}

int main(){
  vector<string> array;
  int n;
  
  cin >> n;
  for(int i=0; i<n; i++){
    string s;
    cin >> s;
    array.push_back(s);
  }
  
  sort(array.begin(), array.end(), compare);
  array.erase(unique(array.begin(), array.end()), array.end());

  for(string a : array){
    cout << a << '\n';
  }
  return 0;
}

정리

sort함수는 <algorithm> 헤더를 include해서 사용할 수 있다.

이 sort 함수의 시간 복잡도는 nlogn이다.

기본적으로 sort(a, b)함수를 사용하면 [a, b) 범위로 오름차순 정렬을 해준다.

sort함수에는 세번째 인자로 bool형을 return하는 compare(i, j)함수를 넣을 수 있다. compare함수를 이용하면 다양한 조건을 활용한 정렬이 가능하다. 위 문제에서 확인할 수 있듯이 compare함수를 이용해서 문자열의 길이를 기준으로 정렬하고 문자열의 길이가 같을 경우에는 알파벳 순으로 정렬하도록 구현할 수 있다.

내림차순으로 정렬하고 싶을 때는 return i>j, 오름차순으로 정렬하고 싶을 때는 return i<j 와 같이 구현하면 된다. 위 코드는 오름차순으로 정렬해야 하므로 return  i<j 로 구현하였다.

 

vector배열 중복 제거하는 법

vector<string> v;
 
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

1. sort로 정렬한다.

2. unique로 연속된 중복원소를 vector의 제일 뒷부분에 쓰레기 값으로 보낸다.

(unique는 vector의 쓰레기 값의 제일 첫부분을 return)

3. erase로 뒤에 붙은 중복원소들을 제거한다.

+(unique는 <algorithm>헤더에 포함되어 있고 erase는 <vector>헤더에 포함되어 있다.

참조

https://aorica.tistory.com/104

https://leeeegun.tistory.com/5

https://dpdpwl.tistory.com/39

https://www.cplusplus.com/reference/algorithm/unique/

https://www.cplusplus.com/reference/vector/vector/erase/