[백준] 단계별로 풀어보기 > 정렬 (c++)

문제 1. 수 정렬하기 (브론즈 1)

• vector로 입력 받아 sort로 정렬

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

using namespace std;

int main() {
	int a, num;
	vector<int> v;
    
	cin >> a;
	
	for (int i = 0; i < a; i++) {
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v.at(i) << "\n";
	}
    
    return 0;
}

 

문제 2. 수 정렬하기 2 (실버 5)

• vector로 입력 받고 sort로 정렬 (1번과 동일)

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

using namespace std;

int main() {
	int a, num;
	vector<int> v;
    
	cin >> a;
	
	for (int i = 0; i < a; i++) {
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v.at(i) << "\n";
	}
    
    return 0;
}

 

문제 3. 수 정렬하기 3 (실버 5)

• map에 입력 받은 수의 개수를 카운팅함

#include<iostream>
#include<map>

using namespace std;

int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    
	int a, num;
	map<int, int> m;
	map<int, int>::iterator iter;
	cin >> a;

	for (int i = 0; i < a; i++) {
		cin >> num;
		if (m[num] == 0) m[num] = 1;
		else m[num]++;
	}

	for (iter = m.begin(); iter != m.end(); iter++) {
		for (int i = 0; i < iter->second; i++) {
			cout << iter->first << "\n";
		}
	}
    return 0;
}

 

문제 4. 통계학 (실버 4)

• 문제 자체는 어렵지 않지만, 함정이 많은 문제였음
• 평균값이 -1과 0 사이에 존재할 경우 별도의 연산이 없으면 -0으로 출력되는 문제가 존재
• 최빈값(가장 많이 나온 값)을 구하고 여러개 일 경우 2번째로 작은 값을 구하는 부분 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<numeric>

using namespace std;

int main() {
	int a;
	double tmp, sum, aver, max, min_val, max_val;

	cin >> a;
	map<double, int> m;
	vector<double> v, v_mode;

	sum = 0;
	for (int i = 0; i < a; i++) {
		cin >> tmp;

		v.push_back(tmp);

		if (m[tmp] == 0) {
			m[tmp] = 1;
		}
		else {
			m[tmp]++;
		}

		sum += tmp;
	}

	aver = accumulate(v.begin(), v.end(), 0.0) / v.size();
	printf("%.0f\n", aver<=0&&aver>-1?(int)aver:aver);

	int cnt = 0;
	int index = (int) floor(a / 2);
	sort(v.begin(), v.end());
	cout << v.at(index) << "\n";

	max = 0;
	for (auto num : m) {
		if (num.second > max) {
			max = num.second;
		}
	}
    
	cnt = 0;
	for (auto num : m) {
		if (num.second == max) {
			v_mode.push_back(num.first);
		}
	}
	
	if (v_mode.size() > 1) {
		sort(v_mode.begin(), v_mode.end());
		cout << v_mode.at(1) << "\n";
	}
	else
	{
		cout << v_mode.at(0) << "\n";
	}

	min_val = v.at(0);
	max_val = v.at(v.size() - 1);
	cout << max_val - min_val << "\n";
    
	return 0;
}

 

문제 5. 소트인사이드 (실버 5)

• vector로 입력받고 오름차순 정렬 후 역으로 출력(내림차순 정렬)

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	vector<char> v;
	string str;
	cin >> str;

	for (int i = 0; i < str.length(); i++) {
		v.push_back(str[i]);
	}

	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	for (auto v_tmp : v) {
		cout << v_tmp;
	}
    
	return 0;
}

 

문제 6. 좌표 정렬하기 (실버 5)

• x좌표로 정렬 후 y좌표 기준 정렬

#include <iostream>
#include <vector>
#include <utility> 
#include <algorithm> 

using namespace std;

int main() {
	int a, b, test_case;
	vector<pair<int, int>> v; 

	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> a >> b;
		v.push_back({a, b});
	}

	sort(v.begin(), v.end());

	for (auto v_tmp : v) {
		cout << v_tmp.first << " "  << v_tmp.second << "\n";
	}
    
    return 0;
}

 

문제 7. 좌표 정렬하기 2 (실버 5)

• y좌표로 정렬 후 x좌표로 정렬
• 문제 6번의 코드에서 입력 받는 순서와 출력 받는 순서만 반대로 해줌

#include <iostream>
#include <vector>
#include <utility> 
#include <algorithm> 

using namespace std;

int main() {
	int a, b, test_case;
	vector<pair<int, int>> v; 

	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> a >> b;
		v.push_back({b, a});
	}

	sort(v.begin(), v.end());

	for (auto v_tmp : v) {
		cout << v_tmp.second << " " << v_tmp.first << "\n";
	}
    
    return 0;
}

 

문제 8. 단어 정렬 (실버 5)

• 문자열의 길이로 먼저 정렬 (map으로 받으면 알아서 오름차순)
• 같은 길이의 문자열을 vector<string>에 받아서 따로 정렬하고 중복은 제거

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

using namespace std;

int main() {
	map<int, vector<string>> m;
	int test_case, str_len, str_len_max=0;
	string str;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		cin >> str;
		str_len = str.length();
		m[str_len].push_back(str);
		if (str_len > str_len_max)	str_len_max = str_len;
	}

	for (int i = 1; i <= str_len_max; i++) {
		sort(m[i].begin(), m[i].end());
		m[i].erase(unique(m[i].begin(), m[i].end()), m[i].end());
	}

	for (int i = 1; i <= str_len_max; i++) {
		for (auto v : m[i]) {
			cout << v << "\n";
		}
	}
    
    return 0;
}

 

문제 9. 나이순 정렬 (실버 5)

• 위 문제와 비슷하게 map의 키값을 나이로 받고 이름을 vector로 받아 입력받은 순서로 출력

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

using namespace std;

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

	int age;
	string name;
	map<int, vector<string>> m;

	for (int i = 0; i < test_case; i++) {
		cin >> age >> name;
		m[age].push_back(name);
	}

	for (auto m_tmp : m) {
		for (auto m_name : m_tmp.second) {
			cout << m_tmp.first << " " << m_name << "\n";
		}
	}
    return 0;
}

 

문제 10. 좌표 압축 (실버 2)

• 좌표를 입력받은 순서로 기록할 vector와 해당 좌표의 압축값을 기록한 map을 활용

#include <iostream>
#include <vector>
#include <algorithm> 
#include <map>

using namespace std;

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

	int tmp;
	map<int, int> m;
	vector<int> v_origin;

	for (int i = 0; i < test_case; i++) {
		cin >> tmp;
		v_origin.push_back(tmp);
	}

    
	vector<int> v_sort(v_origin);
	sort(v_sort.begin(), v_sort.end());
	v_sort.erase(unique(v_sort.begin(), v_sort.end()), v_sort.end());

	for (int i = 0; i < v_sort.size(); i++) {
		m[v_sort[i]] = i;
	}

	for (auto v_tmp : v_origin) {
		cout << m[v_tmp] << " ";
	}
    
	return 0;
}

 

결과