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

 

1. 문제이해

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

10814번: 나이순 정렬

 

온라인 저지 회원의 수(N)와 가입한 사람들의 나이와 이름을 차례로 입력받아,

나이가 어린 순서대로 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

온라인 저지 회원의 수와, 회원들의 나이, 이름을 입력받아 나이순으로 정렬하면 되는 알고리즘이다.

단순히 정렬만 하면 되는 것 아닌가? 하는 생각이 들지만, 문제는 '이름' 까지 입력받는 점이다.

나이순으로 정렬을 하게 되면, 그 나이에 해당되는 회원의 이름까지 함께 정렬되어야 한다.

이처럼, 회원의 나이뿐만 아니라 이름까지 함께 묶어 취급해주기 위해  class를 이용해주었다.

 

문제에서는 나이가 같으면 먼저 가입한 순서대로 출력하라는 조건이 명시되어있다.

여기서 잠깐, 안정정렬과 불안정정렬이라는 개념을 잠깐 짚고 넘어가자.

 

안정정렬은 동일한 값에 대해 기존의 순서가 유지되는 정렬,

불안정정렬은 기존의 순서가 뒤바뀔 수 있는 정렬이다.

즉, 안정정렬은 원래 존재하던 순서를 중시하는 반면, 불안정정렬은 그렇지 않다는 것이다.

C++에서 지원하는 sort함수는 바로 불안정정렬에 해당한다.

 

그렇다면, 문제에서 원하는대로 출력하기 위해서는 어떤 정렬을 사용해야할까?

여기서 필요한 것이 stable_sort 라는 함수이다.

퀵 정렬을 이용하는 sort함수와는 달리 stable_sort함수는 병합정렬을 이용하기 때문에 안정정렬이다.

이 문제에서는 stable_sort 함수를 이용하여 정렬을 해주었다.

 

마지막으로 고려해야할 점은 바로 시간초과에 관한 점이다.

코드를 구현하면서, 계속해서 시간초과가 떴는데, 이를 방지하기 위해 다음과 같은 방법을 써주었다.

 

1. ios::sync_with_stdio(false);  cin.tie(NULL);  cout.tie(NULL);

2. 개행 문자열 endl 대신 '\n' 사용

 

저번 글에서도 언급했지만, cout, cin은 비교적 느린 연산이기 때문에,

연산을 빠르게 해주기 위해 1번과 같은 방법을 사용했다.

또한, endl 연산도 비교적 느린 연산에 해당하므로, '\n'를 사용해 속도를 높여주었다.

 

나는 오늘 이 문제에 대해 두 가지 풀이법으로 풀어보았는데,

한 방법은 stable sort를 사용하지 않은 방법, 다른 한 방법은 stable sort를 이용한 방법이다.

전자는 백준에서는 계속해서 시간 초과가 발생했고, 후자는 맞았다.

후자가 더 좋은 방법일 수 있겠지만, stable_sort를 이용하지 않고 풀었다는 것에 의의를 두며

부끄럽지만 밑의 소스코드 부분에 적어두었다.

(혹시나 첫번째 방법에 잘못된 부분이 있다면 지적은 언제나 환영합니다.😊)

 

 

 

3. 소스코드

1. stable_sort를 이용하지 않은 방법 (시간초과)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

class client {
public:
	int age;
	string name;
};

client* crr = new client[100000];

// agearr, namearr라는 배열을 따로 선언
// class 안에 입력받은 값을 따로 저장해서 비교하기 위함
int agearr[100000];
string namearr[100000];

int main() {

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

	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		cin >> crr[i].age >> crr[i].name;
		agearr[i] = crr[i].age;
		// 값을 입력받아 나이만 agearr에 복사
	}

	// agearr를 정렬
	sort(agearr, agearr + N);

	for (int i = 0; i < N;) {
		for (int j = 0; j < N; j++) {
			// 나이순으로 정렬된 agearr값과 입력받은 class 내의 age값이 같고,
			// 해당 이름값이 empty 가 아니면
			if (agearr[i] == crr[j].age && crr[j].name != "empty") {
				namearr[i] = crr[j].name; // 해당 이름을 namearr에 복사
				crr[j].name = "empty"; // 해당 이름을 empty로 수정
				i++;
				break;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		cout << agearr[i] << " " << namearr[i] << '\n';
	}

	return 0;
}

stable_sort를 이용하지 않은 방법은 전역변수로 배열 두개를 추가로 선언해주었다.

agearr, namearr라는 배열을 두고, class내에 입력된 나이값들만 agearr배열로 복사, 정렬했다.

agearr는 나이순으로 정렬이 된 상태이기 때문에, 이를 통해 본래 class 내의 동일한 age값을 찾고,

나이값이 동일, 이름값이 수정된 상태가 아니라면

해당 부분의 이름값을 namearr에 복사후 empty로 수정해주었다.

 

위 과정을 반복하면, agearr, namearr값이 순서대로 정렬이 되므로,

이를 출력해주면 원하는 결과를 얻을 수 있었다.

백준에서는 이러한 알고리즘을 이용한 방법은 지속적으로 시간초과가 발생했다.😥

 

 

 

2. stable_sort를 이용한 방법 (성공)

#include <iostream>
#include <algorithm>

using namespace std;

// 클래스를 이용해 나이와 이름 한번에 입력받기
class client {
public:
	int age;
	string name;
};

client *crr = new client[100000];

bool cmp(client a, client 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 >> crr[i].age >> crr[i].name;
	}

	// 안정정렬
	stable_sort(crr, crr + N, cmp);

	for (int i = 0; i < N; i++) {
		cout << crr[i].age << " " << crr[i].name << '\n';
	}
	
	return 0;
}

위 방법은 1번의 방법과 비교했을때 훨씬 간단하다.

복사를 위해 사용했던 두가지 배열을 없앴고, 단순히 값을 입력받은 후,

stable_sort를 이용해 정렬한 후 출력해주었다.

다시 보니 코드 수나 전체적인 구조를 봤을때 훨씬 좋은 알고리즘인 것 같기도 하다.

 

 

---

처음에는 1번 방법으로 계속해서 풀다가, stable_sort라는 방법을 알고 꽤나 쉽게 풀었던 문제이다.

하루하루 코딩 공부를 해나가면서 배우는게 정말 많은것같다..

그리고 백준은 시간초과를 참 좋아한다는 것도..😶

다른 분들은 vector를 이용해서도 많이 푸시던데, 아직 vector는 익숙치 않아서 좀 더 연습을 해봐야겠다.