정렬

yeong-min·2022년 6월 1일
[BOJ] 유형별PS
0

Silver 11651

첫시도

#include <iostream>
using namespace std;


int main() {
	int n;
	cin >> n;
	int* x = new int[n];
	int* y = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n - 1; i++) {
			if (y[i] > y[i + 1]) {
				int tmp = y[i];
				y[i] = y[i + 1];
				y[i + 1] = tmp;

				int tmp1 = x[i];
				x[i] = x[i + 1];
				x[i + 1] = tmp1;
			}
			else if (y[i] == y[i + 1]) {
				if (x[i] > x[i + 1]) {
					int tmp2 = x[i];
					x[i] = x[i + 1];
					x[i + 1] = tmp2;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << x[i] << ' ' << y[i] << '\n';
	}
}

답은 나오는데 시간초과!!
n^2번 연산을 하는데
n = 100,000
n^2= 10,000,000,000(100억 번)
1초(1억 번)안에 연산을 해야하므로 시간초과!

두번째시도

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

class Dot {
public:
	int x, y;
	Dot(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

bool compare(Dot a,Dot b) {
	if (a.y == b.y) {
		return a.x < b.x;
	}
	else {
		return a.y < b.y;
	}
}
int main() {
	vector<Dot> v;
	int N,x,y;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		v.push_back(Dot(x,y));
	}
	sort(v.begin(), v.end(), compare);
	for (int i = 0; i < N; i++) {
		cout<< v[i].x<< ' '<<v[i].y << '\n';
	}
	return 0;
}

시간초과를 막기 위해서 헤더파일#include <algorithm>에 있는 sort() 함수와 매개변수로 x,y를 가지고 있는 Dot클래스 이용하여 문제를 해결했다.

Silver 1427

첫시도

#include <iostream>
using namespace std;

int main() {
	string N;
	cin >> N;
	for (int i = 0; i < N.size() - 1; i++)
		for (int j = i + 1; j < N.size(); j++) {
			if (N[i] < N[j]) {
				int tmp = N[j];
				N[j] = N[i];
				N[i] = tmp;
			}
		}
	for (int i = 0; i < N.size(); i++) {
		cout << N[i];
	}
	return 0;
}

자리수를 해결하기 위해 string으로 받고 두개의 for문으로 아스키 코드로 값을 비교하여 내림차순 정렬을 했다.

다른 방법 (Algorithm 헤더파일 이용하기)

#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
    string str;
    cin >> str;
    sort(str.begin(), str.end(), greater<char>());
    cout << str;
}

헤더파일 Algorithm을 추가해주고 sort()함수를 쓰면 기본적으로 오름차순이 되지만 greater<char>()을 써주면 내림차순이 됩니다.

Silver 1181

첫시도

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

using namespace std;
class Alphabet {
public:
	string user;
	int size;
	Alphabet(string user, int size) {
		this->size = size;
		this->user = user;
	}
};
bool compare(Alphabet a, Alphabet b) {
	if (a.size == b.size) {
		return a.user < b.user;
	}
	else {
		return a.size < b.size;
	}
}
int main() {
	vector <Alphabet> v;
	string str;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> str;
		v.push_back(Alphabet(str,str.length()));
	}
	sort(v.begin(), v.end(), compare);

	
	for (int i = 0; i < N; i++) {
		if (i + 1 < N) {
			if (v[i].user == v[i + 1].user) {
				continue;
			}
		}
		cout << v[i].user << '\n';
		
	}
	return 0;
}

구조체와 벡터 sort함수를 이용하여 풀었다 벡터와 클래스 사용 안하고 코드를 더 간단하게 풀수도 있었다.

다른방법(벡터 클래스 사용 X)

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

string word[20000];

bool compare(string a, string b) {
	if (a.size() == b.size()) {
		return a < b;
	}
	else {
		return a.length() < b.length();
	}
}
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word[i];
	}
	sort(word, word + N,compare);
	for (int i = 0; i < N; i++) {
		if (word[i] == word[i - 1]) {
			continue;
		}
		cout << word[i] << '\n';
	}
	return 0;
}

벡터와 클래스 사용 안하고 첫시도에 out of vector range 때문에 if(i + 1 < N)를 추가 하였지만 if (word[i] == word[i - 1])로 간단하게 코드길이를 줄였다
코드길이 700 -> 350 감소

Silver 2108

첫시도

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
int arr[500001];
int number[8001];//0~8000 -4000~4000
int main() {
	int N,max=0,index=0,cnt=0;
	double sum = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum = sum + arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++) {
		number[arr[i] + 4000]++;
	}
	for (int i = 0; i < 8001; i++) {
		if (max < number[i]) {
			max = number[i];
		}
	}
	for (int i = 0; i < 8001; i++) {
		if (max == number[i]) {
			cnt++;
			index = i - 4000;
			if (cnt == 2) {
				index = i - 4000;
				break;
			}
		}
	}
	int avg = round(sum / N);
	if (avg == -0) {
		avg = 0;
	}
	cout << avg << '\n';
	cout << arr[N / 2] << '\n';
	cout << index<<'\n';
	cout << arr[N - 1] - arr[0] << '\n';
	return 0;
}
    1. index (0 ~ 8000) = index-4000 (-4000 ~ 4000)로 숫자 범위를 표현하였다.

최빈값 구할 때 number의 범위가 -4000 <= number <= 4000이므로
number[8001] 배열을 만들어 숫자의 빈도수를 저장하는 배열 생성

    1. 두번째로 작은 최빈값 출력

cnt = 0, cnt++를 이용하여 최빈값이 여러개면 두번째로 작은 최빈 값을 출력하도록 설정

Silver 18870

첫시도

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

int arr[1000000];
int tmp[1000000];
int tmpNumber[1000000];
int main() {
	int N,number=0,a,atmp;
	cin >> N;
	vector<int> v;
	for (int i = 0; i < N; i++) {
		cin >> a;
		arr[i]=a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	tmpNumber[0] = number;
	for (int i = 1; i < N; i++) {
		if (v[i - 1] != v[i]) {
			number++;
			tmpNumber[i] = number;
		}
		else {
			tmpNumber[i] = number;
		}
	}
	for (int i = 0; i < N; i++) {
		atmp = find(v.begin(), v.end(), arr[i]) - v.begin();
		cout << tmpNumber[atmp]<<' ';
	}
	return 0;
}

문제에서 주어진 N의 최댓값이 1,000,000이므로 for문 두개를 사용하면 안됐고 for문을 한번 사용하여 풀었지만 find()함수의 시간 복잡도도 O(N)이라 for문 안에 있으면 시간 복잡도는 O(N^2)이 되므로 시간초과가 되었다.

두번째시도

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



int main() {

	int N,cnt=0,user;
	cin >> N;
	vector<pair<int,int>> v,tmp;
	for (int i = 0; i < N; i++) {
		cin >> user;
		v.push_back(make_pair(user, i));
		tmp.push_back(make_pair(user, i));
	}
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < N; i++) {
		v[i].second = tmp[i].second;
	}
	v[0].first=0;
	for (int i = 1; i < N; i++) {
		if (tmp[i-1].first != tmp[i].first) {
			cnt++;
			v[i].first = cnt;
		}
		else {
			v[i].first = cnt;
		}
	}
	for (int i = 0; i < N; i++) {
		int tmp1 = v[i].first;
		v[i].first = v[i].second;
		v[i].second = tmp1;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < N; i++) {
		cout <<v[i].second << ' ';
	}
	return 0;
}
  1. 문제가 초기의 index를 기억하고 있어야하는 문제이므로 값과 index를 기억 한번에 기억 할 수 있게 pair을 사용하였습니다.
  2. pair을 사용하여 값을 기준으로 오름차순을 해주고 cnt를 각각 대입 해준 후 index를 기준으로 오름차순 해주고 출력을 합니다.

Silver 10989

첫시도

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	
	int N;
	cin >> N;
	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++) {
		cout << arr[i] << '\n';
	}
	delete []arr;

	return 0;
}
  • 메모리 초과!!
    문제에서 주어진 메모리 조건이 8MB = 8,000,000Byte이므로 위 처럼 풀면
    N의 최댓값 10,000,000이 입력되면
    4 X 10,000,000Byte가 필요하므로 메모리 초과가 뜬다!

두번째시도

#include <iostream>

using namespace std;

int arr[10001];
int N;
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		arr[x]++;
	}
	for (int i = 0; i < 10001; i++) {
		while (arr[i]!=0) {
			cout << i << '\n';
			arr[i]--;
		}
	}
	return 0;
}

이번 문제처럼 수의 범위가 작다면 입력받은 수의 배열을 하나씩 카운트 해주어 마지막에 그 숫자만큼 출력해주는 카운팅 정렬을 이용하여 메모리를 적게 사용하여 빠른 정렬을 할 수 있다.

  • 메모리와 시간은 항상 고려하면서 풀기!!
profile
yeong-min
이전 포스트

문자열(String)

다음 포스트

String 기본 개념

0개의 댓글