[백준 BOJ] 10814번 나이순 정렬 (C++/cpp)

문제 설명

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

10814번: 나이순 정렬

 

접근 방법 - 구조체를 응용한 정렬 심화 문제

백준의 10814번 문제는 구조체와 정렬을 함께 고려하여 해결해야 하는 문제이다.

해당 문제는, 입력받은 회원들의 정보를 통하여 나이순으로 회원들을 정렬해야 하는 문제이다.

이번 문제도 나이와 이름을 함께 이동하며 정렬을 수행해야 하는 문제이기 때문에 구조체와 정렬을 함께 사용해보았다.

이런 유형의 문제가 아직 어색하다면 아래 링크의 문제 풀이도 함께 참고해보면 좋을 것이다.

문제의 설명과 입출력만 다를 뿐이지 사실상 원리는 비슷한 문제라 봐도 무방하다.

https://smary-it.tistory.com/200

[백준 BOJ] 5635번 생일 (C++/cpp)

다만 위 링크와는 다른 점이 있다면, 위에선 단순 sort() 함수를 이용했다면 해당 문제에선 stable_sort() 함수를 사용했다는 점이다.

여기서 stable_sort() 함수는 비교하고자 하는 요소 값이 서로 동일하다면 순서를 변경하지 않는 정렬 함수이다.

동일한 나이의 회원끼리는 가입한 순으로 순서를 유지하라고 되어있기 때문에, 필자는 위의 stable_sort()를 통해 해당 문제를 해결하였다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) user 구조체를 만들어 이름(name)과 나이(age)를 멤버로 둔다.

 

2) user 타입에 대한 배열(u)을 전역 변수로 선언해둔다.

 

3) 회원의 수(n)와 그에 따른 회원들의 정보(u)를 순차적으로 입력받는다.

 

4) stable_sort() 함수를 이용하여 user의 나이에 대하여 오름차순 정렬을 한다.

이때, 아래처럼 compare 함수를 선언한 뒤 이를 이용하여 구조체 정렬을 수행하게끔 한다.

(bool형으로 반환하여 각 경우에 대해 위치 변경이 필요한지 아닌지를 결정하게끔 compare 함수를 설정하였다.)

(여기서 나이가 같은 경우에는 가입한 순으로 순서를 유지하라고 하였기 때문에, 이때엔 일반적인 sort() 함수가 아니라 stable_sort() 함수를 사용해야 한다.)

 

5) 정렬한 결과에 따라 순서대로 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 10814번 코드
struct user {
	int age;
	string name;
};
user u[100001];

bool compare(user a, user b) {
	return a.age < b.age;
}

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

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> u[i].age >> u[i].name;
	}
	stable_sort(u, u + n, compare);
	for (int i = 0; i < n; i++) {
		cout << u[i].age << " " << u[i].name << endl;
	}
}

 

제출 결과

(2022.06.19 백준 10814번 문제 제출 결과)