pushback

stable sort에 관한 문제이다.

stable sort란 동일한 값을 갖고 있는 두 원소의 순서가 보장되면서 정렬되는 것이다.

당연하게도 STL에선 stable_sort()라는 함수를 제공한다. sort() 쓰듯이 쓰면 문제를 해결할 수있다. 다만.. 시간이 불만족스럽게 나온다. 

시간을 줄이기 위해서

• string 대신 char 배열 사용 -> 이 문제에선 이상하게 char배열 사용하는게 더 오래걸린다. cin의 문제인 것으로 보임
• 구조체 사용
• stable_sort()대신 sort() 사용

이 외에도 별 짓을 다해봤는데 40ms 안쪽으로 안들어가지더라..

그래서 상위권에 있는 분의 코드를 보니 Queue를 활용한 풀이가 있었다.

먼저 온 사람이 먼저 출력되어야 한다는 점을 착안해서 선입선출 구조를 가진 Queue를 떠올리신 것 같았다.

풀이는 이렇다.

1. 200개의 Queue를 미리 준비 ( queue<string> que[201];)
2. 어떤 사람의 나이와 이름이 입력으로 들어오면, "나이"번째 Queue에 그 사람의 이름을 push.
3. for문을 통해 1부터 200까지 돌면서, Queue가 빌 때까지 나이와 이름을 출력

이렇게 구현하면, 32ms정도 나오게 되고 최적화까지 마치면 28ms까지 줄일 수 있다.

최적화에 대해서 살짝 말하면, 이름을 어딘가에 따로 저장하지말고 입력 들어오는 걸 그대로 Queue에 넣어주면 된다.

(나는 최적화한답시고 Queue를 직접 여러가지 방법으로 구현해봤지만 그대로 32ms가 나왔다)

1. stable_sort()

#include <bits/stdc++.h>

using namespace std;

pair<int, string> profile[100001];

bool compare(const pair<int, string>& p1, const pair<int, string>& p2) {
	return p1.first < p2.first;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
    
	for (int i = 0; i < n; ++i) cin >> profile[i].first >> profile[i].second;
    
	stable_sort(profile, profile + n, compare);
    
	for (int i = 0; i < n; ++i) cout << profile[i].first << ' ' << profile[i].second << '\n';
	return 0;
}

2. 구조체 + char

#include <bits/stdc++.h>
using namespace std;

struct Profile {
	int order;
	int age;
	char name[101];
};

Profile profile[100001];

bool compare(const Profile& p1, const Profile& p2) {
	if (p1.age == p2.age) return p1.order < p2.order;
	return p1.age < p2.age;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
    
	for (int i = 0; i < n; ++i) {
		cin >> profile[i].age >> profile[i].name;
		profile[i].order = i;
	}

	sort(profile, profile + n, compare);
	
	for (int i = 0; i < n; ++i) cout << profile[i].age << ' ' << profile[i].name << '\n';
    
	return 0;
}

3. 구조체 + string

#include <bits/stdc++.h>
using namespace std;

struct Profile {
	int order;
	int age;
	string name;
};

Profile profile[100001];

bool compare(const Profile& p1, const Profile& p2) {
	if (p1.age == p2.age) return p1.order < p2.order;
	return p1.age < p2.age;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
    
	for (int i = 0; i < n; ++i) {
		cin >> profile[i].age >> profile[i].name;
		profile[i].order = i;
	}

	sort(profile, profile + n, compare);

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

4. Queue

#include <bits/stdc++.h>
using namespace std;

string name[100001];
queue<int> que[201];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, age;
	cin >> n;
	
	for (int i = 0; i < n; ++i) {
		cin >> age >> name[i];
		que[age].push(i);
	}

	for (int i = 1; i <= 200; ++i) {
		while (!que[i].empty()) {
			cout << i << ' ' << name[que[i].front()] << '\n';
			que[i].pop();
		}
	}

	return 0;
}

마의 40ms을 넘었다.

5. 배열을 이용해 구현한 Queue

#include <bits/stdc++.h>
using namespace std;

int arr[201][100001];
struct myQueue {
	int age;
	int left;
	int right;

	myQueue() {
		age = 0;
		left = 0;
		right = 0;
	}
	void push(int x) {
		arr[age][right++] = x;
	}

	int front() {
		return arr[age][left];
	}

	void pop() {
		left++;
	}

	void clear() {
		left = 0;
		right = 0;
	}
    
	bool empty() {
		if (left == right) return true;
		return false;
	}
};

string name[100001];
myQueue que[201];

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

	int n, age;
	cin >> n;
	for (int i = 0; i < 201; ++i) que[i].age = i;

	for (int i = 0; i < n; ++i) {
		cin >> age >> name[i];
		que[age].push(i);
	}

	for (int i = 1; i <= 200; ++i) {
		while (!que[i].empty()) {
			cout << i << ' ' << name[que[i].front()] << '\n';
			que[i].pop();
		}
	}

	return 0;
}

문제 해결을 위한 Queue이다보니 각 메서드에서 예외처리는 안해줬다. 안해줘도 이 문제에선 큰 상관 없기 때문에..

6. Singly Linked List를 이용한 Queue 구현

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int data;
	Node* next;
};

Node node[100001];
int cur = 0;

Node* getNewNode(int x) {
	node[cur].data = x;
	return &node[cur++];
}

struct myQueue {
	int age;
	int size;
	Node* head;
	Node* tail;

	myQueue() {
		age = 0;
		size = 0;
		head = nullptr;
		tail = nullptr;
	}

	void push(int x) {
		Node* newNode = getNewNode(x);
		
		if (head == nullptr) {
			head = newNode;
			tail = newNode;
		}
		else {
			tail->next = newNode;
			tail = newNode;
		}

		size++;
	}

	int front() {
		return head->data;
	}

	void pop() {
		head = head->next;
		size--;
	}

	void clear() {
		head = nullptr;
		tail = nullptr;
	}
	bool empty() {
		if (size) return false;
		return true;
	}
};

string name[100001];
myQueue que[201];


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

	int n, age;
	cin >> n;
	for (int i = 0; i < 201; ++i) que[i].age = i;

	for (int i = 0; i < n; ++i) {
		cin >> age >> name[i];
		que[age].push(i);
	}

	for (int i = 1; i <= 200; ++i) {
		while (!que[i].empty()) {
			cout << i << ' ' << name[que[i].front()] << '\n';
			que[i].pop();
		}
	}

	return 0;
}

tail이 추가된 Singly Linked List를 이용한 Queue도 구현해봤다.. 속도엔 큰 영향이 없다.

동적 할당은 속도에 큰 영향을 미치기 때문에, 정적 할당 받은 Node의 주소를 받는 방식으로 진행했다.

7. 가장 빠른 코드 ( STL Queue + string)

#include <bits/stdc++.h>

using namespace std;

queue<string> que[201];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, age;
	string name;
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> age >> name;
		que[age].push(name);
	}

	for (int i = 1; i <= 200; ++i) {
		while (!que[i].empty()) {
			cout << i << ' ' << que[i].front() << '\n';
			que[i].pop();
		}
	}

	return 0;
}

앞서 말했듯이, 10만개짜리 string배열을 없애고 이름을 받는 족족 que에 저장해버린다. 잃어버린 4ms를 여기서 찾을 수 있었다.

번외) 고생한 흔적들