문제를 읽고 그냥 정렬하면 되네~하면 안되는 문제이다. 처음 입력 받은 순서대로 답을 출력해주어야한다.

 

에이~ 그러면 그냥 똑같은 배열 두개 만들어서, 하나는 냅두고 다른 하나는 정렬해서 답 내면 되잖아 ㅋㅋ

 

그런 분들에게 말한다. 이 문제의 핵심은 "나보다 작은 수가 몇개냐?" 이다. 근데 이제 여기에 서로 다른 수가 추가된..

 

자, 밑에 그림과 같이 똑같은 배열 두개가 있고 하나는 정렬되어있는 상태라고 생각해보자.

입력받은 배열을 기준으로 답을 찾아 출력해보자.

  1. 2 보다 작은 서로 다른 수의 개수 = 2
  2. 4 보다 작은 서로 다른 수의 개수 = 3
  3. -10 보다 작은 서로 다른 수의 개수 = 0
  4. 4 보다 작은 서로 다른 수의 개수 = 3
  5. -9 보다 작은 서로 다른 수의 개수 = 1
  6. 6 보다 작은 서로 다른 수의 개수 = 4

혹시 어떻게 \(x\)보다 작은 서로 다른 수의 개수를 세었는가 ? 정렬한 배열에서 하나씩 세셨다면..

어이고... 그러면 최악의 경우에 정렬한 배열을 처음부터 끝까지 다 봐야하는 경우(=\(O(n)\))가 생긴다. 

따라서 시간복잡도가 \(O(n * n) = O(n^2)\)이 되기 때문에 시간초과될 확률이 너무나도 높다.

 

시간복잡도를 줄여보자. 입력받은 배열에서 한번 쭉~ 도는 것을 줄일 순 없다. 

그렇다면, 답을 찾는 시간복잡도를 \(O(n)\)에서 \(O(log n)\) 또는 \(O(1)\)으로 줄여보자.

 

정해라고 생각되는 \(O(1)\)부터 보자.

정렬할 배열의 구성을 좀 바꿔주자. 입력받은 수만 저장하지말고 ( 입력받은 수, index ) 같이 저장하자.

그러면 이렇게 된다.

이제부터 입력받은 배열을 답을 저장한 배열로 바꿔줄 것이다. 어떻게 ???

자, 서로 다른 수의 개수를 저장할 변수(count) 하나를 갖고 정렬한 배열을 처음부터 끝까지 쭈우욱 돌아보자.

 

첫번째 칸은 당연히 자신보다 작은 서로 다른 수가 없기 때문에, 바로 첫번째 칸에 들어있는 index에 접근하여 현재 서로 다른 수의 개수를 넣어주자.

두번째 칸을 보자.가장 먼저 해줄 일은 이전 칸에 저장된 값과 지금 보고 있는 칸에 저장된 값이 다른지? 이다. 

만약 다르다면, 나보다 작은 서로 다른 수의 개수가 하나 더 많아져야한다.

확인이 끝난 후 저장된 인덱스에 접근하여 현재 서로 다른 수의 개수를 저장해주면 된다.

 

이제 계속 똑같이 진행해주면 된다.

 

이전 칸의 저장된 값과 같아 count가 안올라간다.

모든 과정이 끝나고 입력받은 배열만 출력해주면 된다.

#include <bits/stdc++.h>
using namespace std;
struct Pair {
	int number;
	int index;
	
	bool operator< (const Pair& p) {
		return this->number < p.number;
	}
};

int num[1000001]; // 입력받는 배열
Pair ordered[1000001]; // 정렬할 배열

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 >> num[i];
		ordered[i] = { num[i], i };
	}
	
	// 정렬
	sort(ordered, ordered + n);

	int cnt = 0;
	num[ordered[0].index] = cnt; // 첫번째 칸 채우기
    
	for (int i = 1; i < n; ++i) {
		if (ordered[i].number != ordered[i - 1].number) ++cnt; // 이전 칸과 다른 값인지 ?
		num[ordered[i].index] = cnt; // 저장된 인덱스에 접근해서 서로 다른 수의 개수 저장
	}

	for (int i = 0; i < n; ++i) cout << num[i] << ' ';

	return 0;
}


이미 \(O(1)\)에 답을 찾는 방법을 설명했기 때문에, 이 밑에 부분은 그냥 궁금한 분들만 보시면 될 것 같다.

 

\(O(log n)\)방법은 간단하다. 정렬한 배열에서 중복수를 제거하고 이분탐색으로 답을 낼 수 있다.

근데 중복수를 제거할 때,

(중복수인지 확인 = \(O(n)\)) * (제거하는 시간 = \(O(n)\) \(=\) \(O(n^2)\)이라서 시간복잡도가 안줄지 않냐 ? 예리하다.

 

그래서 세 가지 방법이 있다.

  1. \(O(n logn)\)에 중복수 제거 => 배열 정렬 후에 중복되지 않은 수만 다른 vector에 추가
  2. \(O(n)\)에 중복수 제거 => C++의 unique함수
  3. \(O(logn)\)에 중복수 제거 => map 또는 set 컨테이너 사용

이분 탐색은 STL의 lower_bound를 이용하여 내가 원하는 수가 몇번 인덱스에 있는지 확인하면, 그 인덱스가 답이 된다.지적 유희 시간이기 때문에, unique와 lower_bound에 대해선 나중에 설명해보겠다.

 

1. \(O(n logn)\)에 중복수 제거

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

int num[1000001];
int ordered[1000001];
vector<int> vec;

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 >> num[i];
		ordered[i] = num[i];
	}
	// 정렬
	sort(ordered, ordered + n);
	
	vec.push_back(ordered[0]);
	// 중복되지 않은 수들만 vec에 추가
	for (int i = 1; i < n; ++i) if (ordered[i] != ordered[i - 1]) vec.push_back(ordered[i]);

	for (int i = 0; i < n; ++i) cout << (int)(lower_bound(vec.begin(), vec.end(), num[i]) - vec.begin()) << ' ';

	return 0;
}


2.\(O(n)\)에 중복수 제거

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

int num[1000001];
vector<int> ordered;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	ordered.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
		ordered[i] = num[i];
	}
	// 정렬
	sort(ordered.begin(), ordered.end());
	// unique를 이용해 중복 값을 모두 제거
	ordered.resize(unique(ordered.begin(), ordered.end()) - ordered.begin());
	
	for (int i = 0; i < n; ++i) cout << (int) (lower_bound(ordered.begin(), ordered.end(), num[i]) - ordered.begin()) << ' ';
	
	return 0;
}


3 - 1. \(O(logn)\)에 중복수 제거 (map container)

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

int num[1000001];
map<int, int> mp;

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 >> num[i];
		mp[num[i]]++;
	}

	int cnt = 0;
	for (auto it = mp.begin(); it != mp.end(); ++it) {
		it->second = cnt++;
	}

	for (int i = 0; i < n; ++i) cout << mp[num[i]] << ' ';

	return 0;
}


3 - 2. \(O(logn)\)에 중복수 제거 (set container로 중복 제거 후, map에 답을 저장)

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

int num[1000001];
unordered_map<int, int> mp;
set<int> s;

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 >> num[i];
		s.insert(num[i]);
	}

	int sum = 0;
	for (auto it = s.begin(); it != s.end(); ++it) {
		mp[*it] = sum++;
	}

	for (int i = 0; i < n; ++i) cout << mp[num[i]] << ' ';

	return 0;
}


고생의 흔적들

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를 여기서 찾을 수 있었다.

 

 

번외) 고생한 흔적들

1. string를 사용 ( 매우 쉬움 )

2. 구조체 안에 char배열 선언해서 해결하는 방법 ( 쏘쏘 )

3. string + unordered_set을 이용해서 같은 문자열 필터링 ( 속도 얼마 나올지 궁금해서 해본 것 )

 

1. string

#include <bits/stdc++.h>

using namespace std;

bool compare(const string& s1, const string& s2) {
	if (s1.size() == s2.size()) return s1 < s2;
	return s1.size() < s2.size();
}

string str[20001];

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 >> str[i];

	sort(str, str + n, compare);

	cout << str[0] << '\n';
	// 이전에 string과 같으면 출력 X
	for (int i = 1; i < n; ++i) if (str[i - 1] != str[i]) cout << str[i] << '\n';

	return 0;
}

2. 구조체 사용

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

struct Word {
	// 문자열의 길이가 50을 넘지 않으므로 1Byte로도 표현 가능
	char size;
	char str[51];
};

bool compare(const Word& w1, const Word& w2) {
	if (w1.size == w2.size) for (int i = 0; i < w1.size; ++i) {
		if (w1.str[i] == w2.str[i]) continue;
		return w1.str[i] < w2.str[i];
	}
	return w1.size < w2.size;
}

Word word[20001];

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 >> word[i].str;
		word[i].size = strlen(word[i].str);
	}

	sort(word, word + n, compare);

	cout << word[0].str << '\n';
	for (int i = 1; i < n; ++i) if (strcmp(word[i].str, word[i - 1].str)) cout << word[i].str << '\n';
	
	return 0;
}

이 코드는 운 좋게.. 1페이지에 등극했다..

재밌는 점은 printf를 쓰면 20ms가 나오고 cout을 쓰면 16ms가 나온다. fastio의 힘은 대단하다.

 

3. string + unordered_set

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

bool compare(const string& s1, const string& s2) {
	if (s1.size() == s2.size()) return s1 < s2;
	return s1.size() < s2.size();
}

vector<string> vec;
unordered_set<string> us;
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;

	string str;
    
	for (int i = 0; i < n; ++i) {
		cin >> str;
		// 이미 존재하는 문자열인지 확인, 없다면 추가 
		if (us.find(str) == us.end()) {
			us.insert(str);
			vec.push_back(str);
		}
	}

	sort(vec.begin(), vec.end(), compare);

	for (string& str : vec) cout << str << '\n';

	return 0;
}

미친듯이 느리다. 해시함수를 내가 직접 구현하면 좀 더 빠를 수도.. ??

좌표 정렬하기 1과 다르게 이번엔 y좌표를 먼저 보고 x좌표를 본다. 비교함수만 다르게 넣어주면 간단하게 해결할 수  있다.

 

1. 비교 함수 정의

#include <bits/stdc++.h>

using namespace std;

struct Pos {
	int x;
	int y;
};

bool compare(const Pos& p1, const Pos& p2){
    if(p1.y == p2.y) return p1.x < p2.x;
    return p1.y < p2.y;
}

Pos pos[100001];

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 >> pos[i].x >> pos[i].y;

	sort(pos, pos + n, compare);

	for (int i = 0; i < n; ++i) cout << pos[i].x << ' ' <<  pos[i].y << '\n';

	return 0;
}

2. operator< 정의

#include <bits/stdc++.h>

using namespace std;

struct Pos {
	int x;
	int y;

	bool operator< (Pos& p) {
		if (this->y == p.y) return this->x < p.x;
		return this->y < p.y;
	}
};

Pos pos[100001];

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 >> pos[i].x >> pos[i].y;

	sort(pos, pos + n);

	for (int i = 0; i < n; ++i) cout << pos[i].x << ' ' <<  pos[i].y << '\n';

	return 0;
}

3. Pair 클래스

#include <bits/stdc++.h>

using namespace std;

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

pair<int, int> pos[100001];

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 >> pos[i].first >> pos[i].second;
    
	sort(pos, pos + n, compare);
    
	for (int i = 0; i < n; ++i) cout << pos[i].first << ' ' << pos[i].second << '\n';

	return 0;
}

좌표를 저장하는 구조체를 저장하고, 주어진 조건대로 정렬해줄 비교 함수를 작성하면 끝이다.

내가 정의한 구조체를 정렬할 때 비교함수를 직접 작성해도 되고 구조체 안에서 연산자 오버로딩을 해주면 된다.

 

1. 비교함수 작성

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// 좌표를 저장한 구조체
struct Pos {
	int x;
	int y;
};
// 비교함수
bool compare(const Pos& p1, const Pos& p2) {
	if (p1.x == p2.x) return p1.y < p2.y;
	return p1.x < p2.x;
}

Pos pos[100001];

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 >> pos[i].x >> pos[i].y;

	sort(pos, pos + n, compare);

	for (int i = 0; i < n; ++i) cout << pos[i].x << ' ' << pos[i].y << '\n';

	return 0;
}


2. operator< 정의 (연산자 오버로딩)

#include <bits/stdc++.h>

using namespace std;

struct Pos {
	int x;
	int y;

	bool operator< (Pos& p) {
		if (this->x == p.x) return this->y < p.y;
		return this->x < p.x;
	}
};

Pos pos[100001];

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 >> pos[i].x >> pos[i].y;
	// operator<를 정의해주었기 때문에 따로 비교함수가 필요없다
	sort(pos, pos + n);

	for (int i = 0; i < n; ++i) cout << pos[i].x << ' ' <<  pos[i].y << '\n';

	return 0;
}


꿀팁으로 STL에서 제공하는 pair 클래스를 이용하면 굳이 구조체를 정의하지 않아도 된다. 

알고리즘 문제를 해결하다보면 자주 쓰게 되기 때문에 사용법에 익숙해지는 걸 추천드린다.

 

3. pair 클래스

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

pair<int, int> pos[100001];

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 >> pos[i].first >> pos[i].second;
    
	sort(pos, pos + n);
    
	for (int i = 0; i < n; ++i) cout << pos[i].first << ' ' <<  pos[i].second << '\n';
    
	return 0;
}

Pair로 선언된 배열을 정렬할 때 비교함수를 안넣게 되면

  1. first를 기준으로 오름차순으로 정렬
  2. first가 같다면 second를 기준으로 오름차순 정렬

이렇게 정렬해준다. 물론 비교 함수를 따로 작성해주어도 된다.

문제의 의도는 주어진 수를 문자열로 받아 정렬시키는 것으로 보인다...

하지만 수가 고작 10자리이기 때문에, 벡터로도 추우우웅분히 해결 가능하다.

 

1. 문자열로 입력받기

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

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

	string str;
	cin >> str;
    
	sort(str.begin(), str.end(), greater<char>());
    
	cout << str;
	
	return 0;
}

2. int형으로 입력받기

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

vector<int> vec;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int num;
	cin >> num;
    
	// 한자리씩 나누기
	while (num) {
		vec.push_back(num % 10);
		num /= 10;
	}
    
	sort(vec.begin(), vec.end(), greater<int>());
	
	for (int& i : vec) cout << i;
	
	return 0;
}

여러가지 스끼리 필요한 문제다.

 

1. 산술평균

math.h에서 제공하는 round함수를 사용하면 가볍게 소수점 첫째자리에서 반올림을 해준다.

다만, 그러기 위해서 나눗셈의 결과를 int형 변수가 아니라 double형 변수에 저장해야 원하는 결과를 얻을 수 있다. 자명하게도 int형 변수는 소수점 아랫자리가 컷트되기 때문.

 

2. 중앙값

왜 \(n\)이 항상 홀수일까 ?

프로그래밍에서 \(n\)이 홀수일 때, \(n / 2\)은 중앙을 가르키기 때문이다.

무슨 말이냐 ?

5개짜리 배열을 만들면, 인덱스가 0, 1, 2, 3, 4가 만들어진다. int형 변수에 \( 5 / 2\)를 저장하면 저장되는 값은 2.

우연히 5개짜리 배열의 중앙 인덱스 값이 나왔다.

 

7개짜리 배열을 만들어보자. 인덱스가 0, 1, 2, 3, 4, 5, 6이 만들어진다. int형 변수에 \( 7 / 2\)를 저장하면 저장되는 값은 3.

이번에도 우연히 7개짜리 배열의 중앙 인덱스 값이 나왔다.

 

사실 우연이 아니라 자명한 것이다. 이와 같은 성질은 알고리즘 문제를 해결할 때 생각보다 자주 쓰이니까 알아두면 좋다 !

따라서, 중앙값은 정렬되어있는 배열의 \(n / 2\)번째 인덱스에 저장되었는 값이 된다.

 

3. 최빈값

나오는 값의 범위가 \([-4000 , 4000]\)이니까, 어떤 수가 몇 번 나왔는지 체크하는 건 어렵지 않다.

다만, 최빈값이 여러 개라면 두번째로 작은 값을 출력해야되는 것이 까다로울 수 있다.

아이디어는 이렇다. 

  1. 사전에 어떤 수의 등장한 횟수들 중 최댓값을 저장한다.
  2. -4000 ~ 4000까지 돌면서 사전에 구한 최댓값과 같은지 확인한다.
  3. 사전에 구한 최댓값과 같은 수를 두 개째 확인하면 그대로 for문을 종료.

4. 범위

중앙값을 위해 이미 배열을 정렬한 상태라고 가정하자.

정렬되어있다면 첫번째 인덱스와 마지막 인덱스가 각각 최솟값, 최댓값임은 자명하다.

마지막 인덱스에 저장된 값에서 첫번째 인덱스에 저장된 값을 빼주자.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int num[500001];
int cnt[8001];

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

	int n;
	double sum = 0;
	int maxCount = 0;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> num[i];

		sum += num[i];
		maxCount = max(maxCount, ++cnt[num[i] + 4000]);
	}

	sort(num, num + n);

	// 산술평균
	cout << (int)round(sum / n) << '\n';

	// 중앙값
	cout << num[n / 2] << '\n';
	
	// 최빈값
	int modeValue = -4000, numOfMaxCount = 2;
	for (int i = 0; i < 8001 && numOfMaxCount; ++i) if (cnt[i] == maxCount) {
		modeValue = i - 4000;
		numOfMaxCount--;
	}
	cout << modeValue << '\n';

	// 범위
	cout << num[n - 1] - num[0] << '\n';

	return 0;
}

수 정렬하기, 수  정렬하기 2와 다르게 주어진 메모리가 8MB 밖에 없다...

만약 10,000,000개짜리 int형 배열을 선언하면, 40,000,000B = 40,000KB = 40MB 의 메모리가 필요하기 때문에 보나마나 메모리 초과다.

 

다른 조건을 이용하여 풀어야 한다. 입력 조건을 보면 10,000,000개의 수가 주어지고, 각 수는 10,000보다 크지 않은 자연수라고 한다.

첫 조건은 이미 나가리고... 10,000보다 크지 않은 수라는 점을 이용하여 해결하자.

어떻게 해결하지 생각해보니까 간단하다.

어떤 수가 몇 번 등장했는지만 안다면, 우리는 정렬할 수 있다.

 

10,001개짜리 배열 arr을 선언하자.

어떤 수를 입력받았을 때, arr[입력받은 수]에 저장된 값을 +1하자.

입력이 끝나면, for문을 통해 i를 1부터 10,000까지 돌면서 arr[i]에 저장된 값만큼 해당 수를 출력해주면 된다.

 

이와 같이 등장한 수의 개수를 이용한 정렬을 우리는 계수 정렬(Counting Sort)라고 부른다. 이 정렬은 입력 받을 수의 범위를 알아야만 사용 가능하다는 점을 잊지말자 !

#include <iostream>
using namespace std;
int arr[10001] = { 0 , };
int main() {
	ios::ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
    
	int N, tmp;
	cin >> N;
    
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		arr[tmp]++;
	}
    
	for (int i = 1; i <= 10000; i++) {
		// 등장한 적이 없는 수이기 때문에 패스
		if (arr[i] == 0) continue;
        
		// 등장한 만큼 출력
		while(arr[i]--) {
			cout << i << '\n';
		}
	}

	return 0;
}

수 정렬하기 2 문제를 다시 보니, 이 문제 역시 계수 정렬로 해결가능하다 !

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isExist[2000001];

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

	int n, tmp;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> tmp;
		isExist[tmp + 1000000] = true;
	}

	for (int i = 0; i < 2000001; ++i) if (isExist[i]) cout << i - 1000000 << '\n';
	return 0;
}

계수 정렬로 해결하니.. 58등으로 3페이지에 위치할 수 있었다.. 굿

'BOJ_단계별로 풀어보기(9단계~) > [11단계] 정렬' 카테고리의 다른 글

[백준 1427] 소트인사이드  (0) 2022.03.08
[백준 2108] 통계학  (0) 2022.03.08
[백준 2751] 수 정렬하기 2  (0) 2022.03.08
[백준 2750] 수 정렬하기  (0) 2022.03.08
C++ Sort함수  (0) 2022.03.08

+ Recent posts