[C++] 백준 10814번 나이순 정렬

어제에 이어 오늘도 친구들과 도서관에 가기로 한 날이다...

 

...

 

늦잠 자서 샤워만 하고 얼른 도서관에 왔다...

오늘도 파이팅~~

 

문제

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

10814번: 나이순 정렬

 

오늘은 나이순 정렬이라는 문제를 가지고 왔다. 나이가 증가하는 순으로 즉, 오름차순으로 정렬하고 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬을 해야 한다.

 

"그러면 일단 2가지를 입력받아야 하니까 map을 사용하는 것이 좋을 것 같다. map에 n개만큼 입력을 받고 key를 오름차순으로 정렬해야겠다. "라고 생각했는데... 하다 보니까 map을 이렇게 사용하는 게 맞나 싶어서 vector에 pair를 사용하여 각각 지정한 타입으로 값을 저장해 주었다. 각각 다른 정렬 조건으로 정렬을 하고 싶을 때 사용하면 좋다고 한다.

 

이제 코드를 작성해 보자~

 

// 틀린 코드

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

bool comp(pair<int, string> a, pair<int, string> b) {
	return a.first < b.first;
}

int main() {
	vector<pair<int, string>> user;
	int n, age;
	string name;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> age >> name;
		user.push_back(make_pair(age, name));
	}
	sort(user.begin(), user.end(),comp);
	for (int i = 0; i < user.size(); i++) {
		cout << user[i].first<<" "<<user[i].second<<"\n";
	}
	return 0;
}

... 믿을 수가 없어서 한번 더 채점해 달라고 했는데

 

백준: ㅎㅎ 어림도 없지!

 

이번에도 예제가 맞아서 당연히 맞았겠지 했지만...

아니었다... 아무리 봐도 모르겠어서

C++전문가이신 선생님(친구)께 여쭤보았다.

그랬더니 내 코드가 잘못된 이유를 말해주셨다.

 

나는 comp 함수를 작성해 따로 사용자 정의로 정렬해 주었는데, 그렇게 해도 같은 나이인 사람은 뒤에 있는 것을 기준으로 정렬해준다고 한다(사전순으로).

 

... 저렇게 따로 사용자 정의를 해주면 사용자 정의로 되어 있는 것만으로 정렬을 해주는 줄 알았는데.. 아니었다. C++ 전문가이신 나의 선생님은 sort로 정렬할 때 사전순으로 해주는 방법이 있고, 들어온 그대로 정렬해 주는 방법이 있다고 하셨다.

 

그래서 찾아보니 sort는 범위 내에 있는 원소들을 오름차순으로 정렬해 주는 알고리즘이고, 값이 동일한 요소에 대해서는 원래 상대적인 순서(인덱스 번호)를 장담하지 못한다고 한다. 이것을 해결하기 위해 stable_sort를 이용하면 된다. stable_sort는 둘이 같다면 들어온 순서(배열의 순서)에 맞춰 정렬을 해준다. [참고]에 따르면 sort를 사용하면 인덱스도 저장하는 이중 pair 벡터를 만들어서 사용자 정의 함수에서 나이가 같다면 인덱스 번호순으로 나열한다고 조건문을 줬어야 하지만, stable_sort를 사용하면 같은 요소에 대해 인덱스 순으로 정렬하는 성질 때문에 조건문을 따로 쓰지 않고 깔끔하게 표현할 수 있다고 한다.

[참고] https://blahblahlab.tistory.com/34

 

그렇군... 선생님들 감사합니다...

그러면 코드를 다시 수정해 볼까나

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

bool comp(pair<int, string> a, pair<int, string> b) {
	return a.first < b.first;
}

int main() {
	vector<pair<int, string>> user;
	int n, age;
	string name;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> age >> name;
		user.push_back(make_pair(age, name));
	}
	stable_sort(user.begin(), user.end(),comp);
	for (int i = 0; i < user.size(); i++) {
		cout << user[i].first<<" "<<user[i].second<<"\n";
	}
	return 0;
}

 

 

흑... 어렵다 어려워...

아직 배울 것이 많구나

 

+ 추가) pair를 sort 하는 것은 그 안에서 여러 가지 방법으로 정렬해준다고 한다. 그래서 내가 따로 comp 함수를 만들어줘야 하는 것도 앞에만 비교해 주기 위함이라고 한다. 안 만들어준다면 앞에가 같을 때 뒤에 있는 것을 비교해 줄 것이라고...(이렇게 들었는데 맞나??ㅎㅎ)

 

그리고 또 다른 풀이도 알려주셨다(역시... 알고리즘 천재 C++ 전문가 선생님).

그것은 바로!! 3쌍으로 묶어서 입력을 받는 것!!!(세상에!!!)

이것이 무슨 소리인가~~ 하니

나이랑 이름은 그대로 받는데, 가운데에 들어온 순서대로 숫자를 넣어주는 것이다.

즉, (나이, 들어온 순서, 이름) 이런 식으로 말이다.

 

그럼 한번 코드를 작성해볼까~~?

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

int main() {
	vector<tuple<int, int, string>> user;
	int n, age;
	string name;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> age >> name;
		user.push_back(make_tuple(age, i + 1, name));
	}
	sort(user.begin(), user.end());
	for (int i = 0; i < user.size(); i++) {
		cout << get<0>(user[i]) << " " << get<2>(user[i]) << "\n";
	}
	return 0;
}

ㅎㅎ 오예~~ 역시 선생님

 

물론 stable_sort로 작성해도 나온다.

 

여기서 2쌍의 값을 묶는 pair는 기본적으로 존재하고 있어 따로 헤더인 #include <utility>를 추가해주지 않고도 사용할 수 있지만, 3쌍의 값을 묶는 tuple은 헤더 #include <tuple>를 추가해주어야 한다.tuple의 값을 읽기 위해서는 get을 사용한다. get <튜플에서 읽을 인덱스>(튜플)에서 3쌍이기 때문에 <> 안 인덱스는 0~2가 들어갈 수 있다. 그리고 pair는 make_pair이지만 tuple은 make_tuple을 사용하여 생성해야 한다.

 

 

 

다른 풀이도 찾아봐야지

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int,string> a, pair<int,string> b)
{
    return a.first < b.first;
}
int main() {
    int num;
    cin >> num;
    pair<int,string> tmp;
    vector<pair<int,string>> arr;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp.first >> tmp.second;
        arr.push_back(tmp);
    }
    stable_sort(arr.begin(),arr.end(),compare);
    for(int i = 0; i < num; i++)
        cout << arr[i].first << ' ' << arr[i].second << '\n';
}
출처: https://cryptosalamander.tistory.com/52

이 분은 나랑 조금 다른 부분이 있어서 가져와봤다. 나 같은 경우는 변수를 2개 만들어주고 거기에 입력을 받았는데, 이 분은 pair을 이용하여 입력받았다. (오호~ 이렇게도 이용할 수 있구나)

 

다른 분은 구조체를 이용하셔서 가져와보았다. stable_sort를 사용한 것도 있었는데 그건 다 비슷하게 푼 것 같아서 stable_sort를 사용하지 않은 코드를 가져왔다. 게다가 이 코드는 나의 C++ 전문가 선생님께서 말씀하신 다른 방법과 유사해서 한번 살펴보도록 하겠다.

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

struct person
{
    int age, idx;
    string name; //int로 바꿔주면 오류 안남
};

bool compare(const person& now, const person& last)
{
    if(now.age != last.age) return now.age < last.age;
    return now.idx < last.idx;
}

int main()
{	
    ios::sync_with_stdio(false);
	cin.tie(NULL);

    int N;
    cin >> N;
    person people[100001]; //구조체 배열

    for (int i = 0; i < N; i++) //배열에 값 넣어줌
    {    
        cin >> people[i].age >> people[i].name;
        people[i].idx = i;
    }

    //정렬
    //stable_sort(people, people + N, compare);
    sort(people, people + N, compare);

    //답 출력
    for (int i = 0; i < N; i++)
        cout << people[i].age << " " << people[i].name << "\n";
}
출처: https://velog.io/@matcha_/%EB%B0%B1%EC%A4%80-10814-%EB%82%98%EC%9D%B4%EC%88%9C-%EC%A0%95%EB%A0%AC-C-%EC%A0%95%EB%A0%AC

음음 구조체를 만드는데 여기도 idx를 하나 추가해 주셨다. 순서를 체크하려고 넣으신 것이다. 그래서 입력을 받을 때 순서도 같이 넣어주고, 정렬을 하여 앞에 비교할 것이 같으면 다음에는 순서를 비교하게끔 compare 함수를 따로 작성해 주었다. 

 

같은 풀이 방법이라고 하더라도 이런 식으로 다 달라지니 답이 하나라고 생각하지는 말아야겠다는 생각이 들었다.

내일도 파이팅 하자~!

 

 

 

 

 

+ 추가) 자료구조

map과 pair의 차이점

pair: 두 객체를 하나의 객체처럼 다룰 수 있게 해주는 구조
- <utility> 헤더에 존재(utility 선언 안 하고 <vector>를 선언해도 사용 가능)
- 2개를 묶어주는 구조체
- pair 안에 vector 또는 pair 넣기 가능(vector안에 pair 넣기도 가능)
- pair 끼리 비교하면 first를 기준으로 먼저 비교하고, 만약 first가 같다면 second를 비교(sort() 가능)
- pair 끼리 직접 비교는 가능하지만 pair 자체를 직접 더하고 빼고 하는 연산은 불가능

- 사용 방법
   선언: pair <type1, type2> p;
   생성: make_pair(type1 value, type2 value);
   인자 참조: p.first; p.second;

 

 

map: 두 객체를 하나의 객체처럼 다룰 수 있게 해주는 클래스
- <map> 헤더에 존재
- tree 구조
- pair와 동일하게 사용할 수 있지만 key 값 중복 불가
- map의 원소는 pair <key, value> 이므로 pair 객체를 만들어 원소 추가
- key값을 기준으로 원소를 추가, 삭제 
- 이미 있는 key(중복요소)를 insert 하면 false(실패) 반환(insert의 리턴 타입은 pair <iterator, bool>)
- key 값을 직접 바꾸는 것은 불가(바꾸려면 해당 key 삭제 후 다시 insert 해야 함)
- key 값을 배열의 인덱스처럼 사용 가능

- 사용 방법
   선언: map <key, type > m;
   생성: m.insert(make_pair(key_value , type_value)); 또는 m.insert({key_value , type_value});
   참조: m [key] = "값"  // 이런 식으로 값에 접근

 

 

[참고] https://blog.naver.com/oyh951416/222001614292

         https://velog.io/@lamknh/C-map%EA%B3%BC-pair%EC%9D%98-%EC%B0%A8%EC%9D%B4