1181

1181번 : 단어 정렬

#include <iostream>
using namespace std;

int main() {
	int size;
	cin >> size;

	string word[20000];

	for (int i = 0; i < size; i++) {
		cin >> word[i];
	}

	for (int i = 0; i < size-1; i++) {
		for (int j = i + 1; j < size; j++) {
			if (word[i].size() > word[j].size())
				swap(word[i], word[j]);
			else if (word[i].size() == word[j].size()) {
				for (int k = 0; k < word[i].size(); k++) {
					if (word[i].at(k) > word[j].at(k)) {
						swap(word[i], word[j]);
						break;
					}

				}
			}
		}
	}

	string pre;
	for (int i = 0; i < size; i++) {
		if(word[i] != pre)
			cout << word[i] << '\n';
		pre = word[i];
	}

}

위 방법대로 하니 시간초과가 발생하였다. 20000개의 단어를 일일히 비교하게 되므로 시간안에 단어를 비교하기는 무리일 것이다.

따라서 algorithm 라이브러리의 sort함수를 이용하고 vector를 통해 입력된 수만큼만 push 하게끔 하여 간결하게 구현하였다.
sort함수가 단어길이와 알파벳으로 비교할 수 있도록 compareWith 함수를 따로 지정하여 파라미터로 연결하였다.

또한 vector에 단어를 넣을때는 find함수를 통해 vector에서 입력된 단어를 찾아 만약 존재하지 않는다면 push_back함수를 통해 vector에 삽입해준다.

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

bool compareWith(string a, string b) {
	if (a.length() == b.length())
		return a < b;
	return a.length() < b.length();
}

int main() {
	int size;
	cin >> size;
	vector<string> word;

	for (int i = 0; i < size; i++) {
		string str;
		cin >> str;
		if (find(word.begin(), word.end(), str) == word.end())
			word.push_back(str); // find 함수는 해당단어가 존재하지 않으면 end를 반환함
	}
	
	sort(word.begin(), word.end(), compareWith);

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

}

10814

10814번 : 나이순 정렬

pair

이문제는 vector를 이용하되 각 구성요소의 타입이 다른경우이다. 하나는 int 하나는 string 인데, 이를 pair를 통해 다뤄주었다. 나는 이번문제를 통해 처음 접한 클래스인데, utility 라이브러리에 존재한다. 각 구성요소의 첫번째는 first, 두번째는 second로 불러올 수 있다.

stable_sort

sort함수와 stable_sort함수는 다르다. stable하게 소트한다는 것은 각 자리수까지 고려한다는 것이다. 예를 들어 12, 11, 20, 30 을 비교할때, 그냥 소트함수를 사용하게 되면 11과 12를 같은 선상에 두고 sort하게 될 수 있다. 그러나 stable_sort를 사용하면 확실히 11 < 12 를 구별하게 된다. 사용법은 sort함수와 같다.

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

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

int main() {
	int N;
	cin >> N;

	vector<pair<int, string>> crew(N);
	for (int i = 0; i < N; i++) {
		cin >> crew[i].first >> crew[i].second;
	}

	stable_sort(crew.begin(), crew.end(), compareWith);

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