백준 단계 13 : 정렬 (C++)

2750. N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> num(n);
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    sort(num.begin(), num.end());
    for (int i = 0; i < n; i++) {
        cout << num[i] << '\n';
    }
}

c++의 내장함수인 sort 함수를 이용하여 정렬하였다.

 

https://shine-slowly.tistory.com/37

알고리즘 : 정렬이란? (C++로 구현)

직접 정렬 함수를 구현해서 사용해도 된다. 정렬 관련 함수는 위에 정리해두었다. 글이 길기 때문에 특정 정렬만 궁금하다면 ctrl+f를 하는 것을 추천한다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void insertionSort(vector <int>& list, int n) {
    for (int i = 1; i < n; i++)
    {   
        int key = list[i];
        int j;
        for (j = i-1; j >= 0 && list[j]> key; j--)
        {
            list[j + 1] = list[j];
        }
        list[j + 1] = key;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> num(n);
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    insertionSort(num, n);
    for (int i = 0; i < n; i++) {
        cout << num[i] << '\n';
    }
}

삽입정렬을 이용하여 작성하였다. vector 값을 변경하고 싶은 경우에는 참조에 의한 호출 (call by reference)을 이용해야 한다.

 

 

 

2587. 다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void selectionSort(int list[], int n) {
    for (int i = 0; i < n; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (list[minIndex] > list[j])
                minIndex = j;
        }
        if (i != minIndex)
            swap(list[i], list[minIndex]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int num[5];
    int sum = 0;
    for (int i = 0; i < 5; i++)
    {
        cin >> num[i];
        sum += num[i];
    }

    selectionSort(num, 5); // sort(num, num+5);도 가능
    cout << sum / 5 << '\n' << num[2];
}

이번엔 선택정렬을 이용하여 구현하였다.

 

 

 

25305. 이들 중 점수가 가장 높은 k명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void insertionSort(vector<int>& list, int n) {
    for (int i = 1; i < n; i++)
    {
        int key = list[i];
        int j = i - 1;
        while (j >= 0 && list[j] > key) {
            list[j + 1] = list[j];
            j--;
        }
        list[j + 1] = key;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <int> score(n);
    for (int i = 0; i < n; i++)
    {
        cin >> score[i];
    }

    insertionSort(score, n); // sort(score, score+n);으로도 구현 가능
    cout << score[n - k];
}

삽입 정렬을 이용하여 구현하였다. 마찬가지로 내장함수를 사용해도 된다. 굳이 정렬 함수 구현하는 이유는 연습을 위해서 이다.

 

 

 

2751. N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> num(n);
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num.begin(), num.end());

    for (int i = 0; i < n; i++)
    {
        cout << num[i] << '\n';
    }
}

시간 복잡도는 1억당 1초 정도로 생각할 수 있다. n이 1억이고 O(n)이면 1초 정도 걸리는 것이고, n이 1억, m이 10이면 10억이므로 O(nm)은 10초 정도 걸리게 되는 것이다. 1억은 100,000,000으로 0이 8개이다. 시간 제한이 2초이고 n이 1,000,000 이하로 주어졌기 때문에 O(n^2)로는 구현할 수 없다.

c++의 sort 함수는 quick sort로 O(nlogn)이다. 내장함수를 이용하여 구현하였다.

 

 

 

10989. N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> num(10000, 0);
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        num[temp - 1]++;
    }
    for (int i = 0; i < 10000; i++)
    {
        if (num[i] != 0) {
            for (int j = 0; j < num[i]; j++)
            {
                cout << i + 1 << '\n';
            }
        }
    }
}

sort() 함수를 사용하면 메모리 초과가 발생한다. 최대 N이 10,000,000이므로 입력값을 모두 저장하면 메모리가 부족해진다. 10^7 * 4byte = 40MB이기 때문이다.

cin.tie(0)을 해주지 않으면 위 코드도 시간초과가 발생한다고 한다. 이중 for문을 사용해서 O(n^2)가 되기 때문이다.

 

 

 

1427. 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string num;
    cin >> num;
    vector <int> rNum(num.length());
    for (int i = 0; i < num.length(); i++)
    {
        rNum[i] = num[i] - '0';
    }
    sort(rNum.begin(), rNum.end(), greater<>()); // 내림차순
    for (int i = 0; i < num.length(); i++)
    {
        cout << rNum[i];
    }
}

나는 숫자로 변환하는 과정을 거쳤으나 아래와 같은 코드로 쉽게 작성할 수도 있었다

 

int main() {
    string str;
    cin>>str;
    sort(str.begin(), str.end(), greater<char>());
    cout<<str;
}

greater<>()를 이용하면 내림차순으로 정렬할 수 있다. C++ 14부터는 greater<int>()가 아닌 greater<>()과 같이 타입을 명시해주지 않아도 된다.

 

 

 

11650. 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x, y;
    cin >> n;
    vector <vector <int>> xy(n, vector<int>(2));    
    for (int i = 0; i < n; i++)
    {
        cin >> xy[i][0] >> xy[i][1];
    }

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

    for (int i = 0; i < n; i++)
    {
        cout << xy[i][0] << " " << xy[i][1] << '\n';
    }
}

c++ sort 함수를 사용하면 알아서 x를 기준으로 정렬이 되고 같은 경우 y가 작은 것이 앞으로 온다.

 

bool cmp(vector<int>& v1, vector<int>& v2) {
    if (v1[1] == v2[1])
        return v1[0] < v2[0];
    else return v1[1] < v2[1];
}

sort(xy.begin(), xy.end(), cmp);

만약 y를 기준으로 정렬하고 싶다면 이 코드를 추가해야 한다. 

 

* 2차원 벡터 선언법 *

vector<vector<int>> v1(n,vector<int>(m)); // N*M만큼 2차원 벡터 공간만 확보
vector<vector<int>> v2(n,vector<int>(m,0)) // N*M만큼 2차원 벡터 0으로 값

기본적인 2차원 벡터 선언이다.

vector<pair<int,int>> v; // pair를 원소로 가진 벡터 선언
v.push_back(make_pair(1,2));
v.push_back({3,4});
v[i]={5,6};

cout<<v1[i].first<<" "<<v1[i].second<<'\n';

pair은 두개의 객체를 하나로 묶어주는 역할을 한다. first와 second로 접근하여 출력할 수 있다.

pair<int,int> p; // int,int형 pair p를 선언함

단독으로 pair을 사용 할 수도 있다.

 

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		v.push_back({ x, y });
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		cout << v[i].first << ' ' << v[i].second << '\n';
	}
	return 0;
}

pair을 사용한 코드이다. 알아서 first 순으로 오름차순 정렬하고 first가 같을 경우 second를 따진다.

 

 

 

11651. 2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
bool compare(pair<int, int> v1, pair<int, int> v2) {
    if (v1.second == v2.second)
        return v1.first < v2.first;
    else
        return v1.second < v2.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x, y;
    cin >> n;
    vector <pair <int, int>> v;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        v.push_back({ x, y });
    }
    sort(v.begin(), v.end(), compare);

    for (int i = 0; i < n; i++)
    {
        cout << v[i].first << " " << v[i].second << '\n';
    }
    return 0;
}

위에서 언급했던 내용이 이 문제에 나왔다. 쉽게 풀 수 있는 문제이다.

 

 

 

1181. 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
bool compare(string s1, string s2) {
    if (s1.length() == s2.length())
        return s1 < s2;  
    else
        return s1.length() < s2.length();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

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

    for (int i = 0; i < n; i++)
    {
        if ((i > 0) && (v[i] == v[i - 1]))
            continue;
        cout << v[i] << '\n';
    }
    return 0;
}

string 형을 >나 <를 통해서 사전식 비교를 할 수 있다. 중복된 경우는 한번만 출력하도록 설정하였다. find 함수를 구현하신 분도 있었는데 find 함수를 까먹어서 다시 다뤄보고자 한다. string의 find 함수가 아니다.

 

<algorithm>의 find()함수

#include <algorithm>
find(begin, end, value);

begin ~ end 의 원소 중(end는 포함되지 않음)에 value에 해당하는 주소를 반환한다. 일치하는 원소가 없을 경우에는 end가 반환된다. 

 

<string>의 find()함수

#include <string>
string str;
str.find(value);

문자열 내에서 value 값을 찾고 일치하는 값이 있다면 value의 첫번째 인덱스를 반환한다.

 

for(int i=0; i<n; i++){
    string str;
    cin>>str;
    if(find(v.begin(), v.end(), str) == v.end())
      v.push_back(str);
}

일치하는 원소가 없을 경우에는 end가 반환되는 것을 이용하여 작성한 코드이다.

 

 

 

10814. 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
bool compare(pair<int, string> p1, pair<int, string> p2) {
    return p1.first < p2.first;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <pair<int, string>> v;
    int age;
    string name;
    for (int i = 0; i < n; i++)
    {
        cin >> age >> name;
        v.push_back({ age , name });
    }
    stable_sort(v.begin(), v.end(), compare);
    for (int i = 0; i < n; i++)
    {
        cout << v[i].first << " " << v[i].second << '\n';
    }
}

sort 함수를 사용해도 입력한 순서대로 잘 출력이 되는데 틀렸다고 해서 그 이유를 찾아봤다. 

sort는 두 값이 같을 때 기존의 순서를 유지하는 것을 보장하지 않는데, 보장하지 않는다는 것은 순서가 뒤바뀌었을 때 틀릴 수 있는지 실행하지 않고도 직접 판단할 수 없도록 만들기 때문에 틀린다고 한다. 

sort에 의한 원소의 상대적인 순서 변경은 가능성에 불과하다는 것이다. 따라서, 상대적인 순서가 중요한 경우에는 안정적인 정렬 알고리즘인 stable_sort를 사용하는 것이 좋다. stable_sort()함수는 merge 정렬를 통해 수행한다.

 

 

18870. 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n;
    vector<int> v, temp;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        temp.push_back(x);
        if (find(v.begin(), v.end(), x) == v.end()) {
            v.push_back(x);
        }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++)
    {
        int count = find(v.begin(), v.end(), temp[i]) - v.begin();
        cout << count << ' ';
    }
    
}

처음 작성한 코드이다. 시간초과가 뜬다. find 함수는 순차탐색이라 O(n)이다.

 

<unique 함수>

연속으로 중복되는 원소를 vector의 제일 뒷부분으로 보낸다.

{1, 2, 2, 3, 4, 4, 5}와 같은 벡터 v가 있다고 가정하자.

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

연속으로 중복되는 2와 4가 제거되고 나머지 자리에는 기존벡터배열 원소값이 채워진다. 

즉 {1, 2, 3, 4, 5, 4, 5}가 되고 뒤에서 두번째에 있는 4를 반환하게 된다.

 

<vector의 erase 함수>

erase로 뒤에 붙은 값을 제거해줄 수 있다. unique가 끝나면 반환되는 값이 불필요한 값의 첫번째 위치가 되는데 이를 이용하면 erase로 그 주소부터 끝까지 지울 수 있는 것이다.

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

https://velog.io/@cse_pebb/C-remove-%ED%95%A8%EC%88%98-vs.-vector%EC%9D%98-erase-%ED%95%A8%EC%88%98

[C++] vector의 값 지우기 - remove() 함수 vs. vector의 erase() 함수

 

<lower_bound 함수>

이미 정렬된 곳에서 탐색하는 경우 이진 탐색으로 구현된 lower_bound()를 사용하는 것이 좋다. 이진탐색은 O(logn)이다.

처음 n값이 나오는 위치를 반환한다.

lower_bound(v.begin(), v.end(), 5); // 찾고자 하는 값이 5

찾고자 하는 값이 있는 곳의 주소를 반환하게 된다.

 

#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n;
    vector<int> v, temp;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    temp = v;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i < n; i++)
    {
        cout << lower_bound(v.begin(), v.end(), temp[i]) - v.begin() << " ";
    }
    
}

최종 코드이다.