BOJ 10814

첫 접근 방법

맘에 안드는 풀이입니다. 토크나이저를 연습하려고 굳이 빙빙 돌아갔는데 시간 초과가 발생했어요.

• 시간 초과는 아마 cin, cout에서 발생한 것으로 보입니다.
  - 👉 확인해보니 endl을 사용해서 발생한 시간 초과입니다.
  - 이를 수정하고 돌려보면 아래의 풀이도 분명 맞는 풀이입니다. (하지만 너무 긴게 문제죠!)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <sstream>

using namespace std;

struct node {
	int age;
	int time;
	string name;
};

bool comp(node a, node b) {
	if (a.age == b.age) {
		return a.time < b.time;
	}
	else
		return a.age < b.age;
}

int main() {
	int n;
	cin >> n;
	vector <node> arr;

	cin.ignore(); // 공백, 엔터 같은 것을 무시

	for (int i = 0; i < n; i++) {
    // 입력 받기 
		string temp;
		getline(cin, temp);

    // 토크나이징 준비
		stringstream str(temp);
		string buffer;
		struct node nd;
		int idx = 0; 

    // tokenize (굳이 할 필요가 없는데..ㅠㅠ)
		while (getline(str, buffer, ' ')) {
			if (idx == 0) {
				nd.age = stoi(buffer);
			}
			if (idx == 1) {
				nd.name = buffer;
				nd.time = i;
			}
			idx++;
		}
		arr.push_back(nd);
	}

  // 정렬
	sort(arr.begin(), arr.end(), comp);

  // 출력
	for (int i = 0; i < n; i++) {
		cout << arr[i].age <<" " << arr[i].name<< endl;
	}
}

미흡한 점

• tokenizer를 체화하기 위해 연습으로 풀었으나 시간초과가 발생했습니다.

• time 순으로 정렬하는 조건도 있어서 구조체를 직접 만들었습니다.

• 굉장히 비효율적으로 구문들을 나누고 있습니다.

배운 점

• 또한 시간 저장을 위해 struct에 time을 생성했으나, stable_sort를 이용하면 index가 유지된 채로 완전한 sort가 이루어짐을 학습을 통해 배웠습니다.
  - 👉 굳이 구조체를 선언해서 time을 만들어줄 필요가 없는거죠!

• input으로 들어오는 type이 정해져 있다면 cin으로 그에 맞게 받아주면 됩니다.

• cout, cin을 최적화해줍시다.

• 출력이 많은 경우 endl 사용을 금지합니다. 시간이 오래걸립니다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

bool comp(pair<int, string> a, pair<int, string> b) {
	return a.first < b.first;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	pair<int, string> info;
	vector<pair<int, string>> arr;

	for (int i = 0; i < n; i++) {
		cin >> info.first >> info.second;
		arr.push_back(info);
	}

	stable_sort(arr.begin(), arr.end(),comp);

	for (auto itr : arr) {
		cout << itr.first << " " << itr.second << '\n';
	}

	return 0;
}