#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;
}
만약 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;
}
#include <iostream>
#include <algorithm>
using namespace std;
int num[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];
sort(num, num + n);
for (int i = 0; i < n; i++) cout << num[i] << '\n';
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
int num[1000];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> num[i];
sort(num, num + n);
for (int i = 0; i < n; i++) cout << num[i] << '\n';
return 0;
}
sort함수는 세 개의 인자를 받습니다. sort(배열의 시작, 배열의 끝, 정렬 방법) 이라고 생각하시면 편합니다. 세번째 인자를 생략하면 자동 오름차순으로 정렬됩니다.
좀 더 정확히 설명해봅시다.
int arr[5] = { 4, 3, 2, 1, 0 };
int형 원소들을 갖고 있는 arr배열을 오름차순으로 정렬하고싶다면,
sort(arr, arr + 5);
이 코드 한줄로 끝나게 됩니다.
한가지 의문이 듭니다. 왜 배열의 끝이 arr + 4가 아니라 arr + 5일까 ?
밑에 그림을 보겠습니다.
간단하쥬 ? 이 그림이 이해가 안가신다면 포인터 개념을 공부해주시면 됩니다.
이번엔 vector를 이용해봅시다.
vector<int> vec = { 4, 3, 2, 1, 0};
위에 배열과 같은 원소를 갖는 vector를 만들었습니다.
마찬가지로 오름차순으로 정렬하고 싶습니다.
sort(vec, vec + 5);
하면 에러입니다.
vector는 STL에서 제공하는 자료구조이기 때문에 iterator(반복자)를 인자로 넣어주어야 합니다.
sort(vec.begin(), vec.end());
이 옳은 방법입니다.
혹시 vector에서 모든 원소 정렬이 아닌 원하는 부분만 정렬하고 싶다면,
sort(vec.begin() + a, vec.begin() + b);
와 같은 방식으로 a부터 b - 1번째 원소들만 정렬할 수 있습니다.
이번엔 세번째 인자에 대해 알아봅시다.
sort함수가 수행될 때, 어떤 기준으로 정렬이 될 지 정해주는 부분입니다.정의하는 방법은 세 가지 정도 있지만, 가볍게 함수로 정의하는 방법만 보겠습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(int& a, int& b){
// (a보다 b가 더 크면 true, 아니면 false) == 오름차순
return a < b;
}
int arr[5] = {4, 3, 2, 1, 0};
vector<int> vec = {4, 3, 2, 1, 0};
int main(){
sort(arr, arr + 5, compare);
sort(vec.begin(), vec.end(), compare);
return 0;
}
보시는 것처럼 간단합니다. 같은 자료형 두 개를 인자로 받고, bool값을 리턴해주는 함수를 작성해주면 비교함수 완성.
return a > b; 를 하면 당연하게도 내림차순으로 정렬됩니다.
살짝 tip 아닌 tip을 드리자면 STL에서 제공하는 functional 라이브러리 안에 less<자료형>()과 greater<자료형>() 함수가 있습니다. 매번 compare함수를 작성하는게 귀찮으신 분들은 이 두 함수를 이용하셔도 되지만, 단순한 내림차순 오름차순 정렬임을 유의해주셔야합니다.
하지만, 알고리즘 문제를 해결할 때마다 구현하는 것은 굉장한 시간 낭비일 것입니다. 따라서 저는 algorithm 라이브러리에서 제공하는 sort함수를 사용하여 12단계의 문제들을 해결할 예정입니다.
제가 올리는 글에선 sort함수 사용방법을 배우시고, 만약 위에 언급된 6개 정렬 중 모르는 것이 있다면 꼭 공부해보시는 것을 추천드립니다.
백준에서 제공하는 일반적인 알고리즘 문제에선 sort 함수로도 충분히 통과가 가능하지만, 삼성 B형 테스트와 같이 메모리와 시간 최적화가 필요한 문제들은 스스로 정렬 알고리즘을 구현할 줄 알아야 하기 때문입니다. 시간이 허락한다면, 저도 제가 구현한 코드를 사용하여 문제들을 해결해보도록 하겠습니다. 감사합니다.
첫번째 방법은 666이 포함된 수를 오름차순으로 찾을 수 있기 때문에 편하지만, 666이 포함되었는지 확인하는 방법이 조금은 난감하다.
여기서 다시 두 가지로 나눌 수 있다.
1-1. to_string를 이용하여 숫자를 string으로 변환한 다음, string.find를 이용하여 "666"이란 문자열을 포함하는지 확인하는 방법.
1-2. 나머지 연산으로 1의 자리에서부터 3자리씩 보면서 666인지 확인하는 방법이다.
1-1)코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int cnt = 0, ans = 0;
for (int i = 666; cnt < n; i++) {
string str = to_string(i);
if(str.find("666", 0, 3) != string::npos){
cnt++;
ans = i;
}
}
cout << ans;
return 0;
}
코드 자체는 간결하지만 string을 사용하기 때문에 cost가 꽤나 크다.
1-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; }
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int cnt = 0, ans = 0;
for (int i = 666; cnt < n; i++) {
int num = i;
// 뒤에서부터 3자리씩 보면서 666을 포함하는지 확인
while (num) {
int left = num % 1000;
if (left == 666) {
cnt++;
ans = i;
break;
}
num /= 10;
}
}
cout << ans;
return 0;
}
연산을 통해 666이 있는지 확인하기 때문에 1-1방법에 비해 비약적으로 속도를 줄일 수 있다.
두번째 방법은 쉽지만 어렵다. 정확히 말하면 개념은 쉽지만 구현이 살짝 어지럽다. WHY ?
둘) int형 변수에 0666은 666으로 저장된다. - 이건 왜 ? 0666을 무시하는 순간 우리는 10666을 평생 만들 수 없다.
중복 수는 해결하기 쉽지만 두번째 문제는 ... 이게 뭘까싶다. 해결하기위해 우리가 0666을 무시했을 때 만들지 못하는 숫자들을 관찰해보자.
5자리 수 : 10666, 20666, 30666, ... 90666
6자리 수 : 100666, 101666, 102666, ... , 200666, ...
이런 숫자들이다. (사실 110666도 못만드는 숫자지만, 10666을 만들 수 있다면 110666은 자동적으로 추가되는 숫자라 제외했다.)
자세히 보자.
5자리 수 : 10666, 20666, 30666, ... 90666
6자리 수 : 100666, 101666, 102666, ... , 200666, ...
관찰 결과 : \(n\)자리 수를 만들려고 할 때, 이미 만들어진 모든 수에 \( 1\times10^{n - 1}, ... , 9\times10^{n - 1}\)를 더해주자.
따라서 666을 포함한 n자리의 수를 만드는 방법은,
1. 이미 만들어진 모든 수에 \( 1\times10^{n - 1}, ... , 9\times10^{n - 1}\)를 더한 수
2. 666을 포함한 n - 1자리의 수 앞에 0~9을 추가한 수
3. 666을 포함한 n - 1자리의 수 뒤에 1~9을 추가한 수
4. 중복 수 제거이다.
살짝 최적화를 해본다면, 2번에서 만들어지는 모든 수는 이미 1번에서 만들어져 있기 때문에 1, 3, 4만 진행하면 된다.
최적화를 조금 더 해본다면, set를 쓴다면 중복 수는 자동적으로 무시되기 때문에 1, 3만 진행하면 된다.
#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; }
// 10,000번째 수까지만 보기 때문에 7자리의 수들까지만 봐도 충분하다.
set<int> num[8]; // num[i]에는 666을 포함한 i자리 수들을 저장하고 있다.
int main() {
ios::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int cnt = 1;
num[3].insert(666);
for (int i = 4; i < 8 && cnt < n; ++i) {
int pos = (int)pow(10, i - 1);
// 앞에 추가
for(int from = 3; from < i; ++from)
for (int prev : num[from])
for (int j = 1; j < 10; ++j)
num[i].insert(j * pos + prev);
// 뒤에 추가
for (int prev : num[i - 1]) for (int j = 0; j < 10; ++j) num[i].insert(prev * 10 + j);
cnt += num[i].size();
}
for (int i = 3; i < 8; ++i) {
if (n > num[i].size()) n -= num[i].size();
else {
// set는 index접근이 불가능하기 때문에 iterator를 사용
set<int>::iterator it = num[i].begin();
for (int i = 1; i < n; ++i) ++it;
cout << *it;
break;
}
}
return 0;
}
