[ 백준 / C++ ] 1181 단어 정렬 + sort()

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

1181번: 단어 정렬

1. sort 설명

2. 정답 코드 << 바로 정답 보고 싶으신 분은 정답 코드 클릭

 

아직 C++ 언어가 어색해서 걱정인데, 

그 중 알고리즘에서 가장 중요한 sort()에 대해 한 번 알아보려 한다.

이걸 몰라서 신한 코테에서 개고생을 했었다..;

 

sort는 algorithm STL에서 제공하고 있다.

#include < algorithm>

하지만 저는 bits/stdc++.h를 사용합니다 개편한~

 

1. sort algorithm

sort(start, end, compare)로 되어 있다. 이 때, start와 end에는 주소값이 와야 한다. 

compare를 넣지 않을 경우 오름차순 정렬이 되고, 내림 차순 정렬의 경우 compare 위치에 greater<자료형>()을 넣어준다.

sort는 quick sort 기반으로 함수가 구현되어 있어 평균 시간 복잡도는 n log n이다. 

[start, end)로 end는 포함되지 않는다. 

 

2. 배열에서의 사용

#include<iostream>
#include<algorithm>
using namespace std;
void Print(int *arr){
    cout << "arr[i] : " ;
    for(int i=0; i<10; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main(void){
    int arr[10] = {3, 7, 2, 4, 1, 0, 9, 8, 5, 6};
    sort(arr, arr+10); //[arr, arr+10) default(오름차순)로 정렬
    Print(arr); //정렬 후 출력
    
    return 0;
}

// arr[i] : 0 1 2 3 4 5 6 7 8 9

3. vector에서 사용 

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
using namespace std;
 
void Print(vector<int> &v){
    cout << "vector : " ;
    for(int i=0; i<10; i++){
        cout << v[i] << " ";
    }
    cout << endl;
}
 
int main(void){
    srand((int)time(NULL)); //난수생성을 위해
    
    vector<int> v;
    int n = 10;
    
    for(int i=0; i<n; i++){ //vector에 1의자리 숫자를 임의로 삽입
        v.push_back(rand() % 10);
    }
    sort(v.begin(), v.end(), greater<int>()); //[begin, end) 내림차순으로 정렬
    Print(v); //정렬 후 출력
    
    return 0;
}

// vector : 9 8 7 6 5 4 3 2 1 0

4. compare 함수 직접 생성

compare 함수에 대한 예제는 문제의 정답에서 확인하세요

++ 추가하자면, 혹시 받는 파라미터의 자료형이 vector<> 와 같은 복잡한 구조라면 

compare 함수에서 call-by-value가 아닌 call-by-reference를 사용하길 추천합니다 : )

bool compare(vector <int> &v1, vector<int> &v2 )
이렇게 말이죠 ㅎㅎ 앞에 const를 붙여준다면 변경될 걱정도 없습니다. 

bool compare(cons vector<int> &v1, const vector<int> &v2)

 

[정답]

#include <bits/stdc++.h>

using namespace std;

int N;
vector<string> arr;
map<string, int> marr;

bool compare(string s1, string s2) {
	if (s1.length() > s2.length()) {
		return false;
	}else if (s1.length() == s2.length() && s1 > s2) {
		return false;
	}
	return true;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		if (marr[s] == 0) {
			marr[s] += 1;
			arr.push_back(s);
		}
	}

	sort(arr.begin(), arr.end(), compare);
	for (auto i : arr) cout << i << '\n';
}