#include <bits/stdc++.h>
using namespace std;
int n;
string st;
vector<string> v;
bool cmp(string &a, string & b){
if(a.size() != b.size()) return a.size() < b.size(); // 길이 짧은것 우선
else return a < b; // 사전순
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) {
cin >> st;
v.push_back(st);
}
sort(v.begin(), v.end(), cmp);
v.erase(unique(v.begin(), v.end()), v.end());
for(auto i : v) cout << i << '\n';
return 0;
}
리뷰
중복을 제거하는 것은 unique와 erase를 썼는데 이번에 풀면서 배웠다. unique 를 쓰면 중복은 제거되도 벡터의 크기가 줄어들지는 않는다. unique는 중복되는 원소의 포인터를 맨 뒤로 보내기 때문이다. unique의 리턴 값은 중복 제거 된 원소의 포인터다. 그래서 erase로 중복 제거된 원소의 포인터 부터 맨 마지막 포인터까지 공간을 삭제해준다. erase를 하면 아예 메모리가 해제되니까 중복된 부분의 크기만큼 반환되는 것이다.
#include <bits/stdc++.h>
using namespace std;
int n, num;
int arr[2000002];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> num;
arr[num+1000000]++;
}
for(int i = 0; i <= 2000000; i++) {
while(arr[i] > 0) {
cout << i-1000000 << '\n';
arr[i]--;
}
}
return 0;
}
리뷰
절대값이 100만 이하인 정수가 입력으로 들어오니까. 양수 음수 처리를 따로 해야겠다고 생각했었다. 일단 정답 코드를 제출하고 다른 분의 코드를 봤다. 200만 크기의 배열을 쓰면서도 어차피 입력받은 대로 더하고 빼주고 하면 입력 받은 숫자를 출력할 수 있으니까. 입력받을 때 저장하는 인덱스 : num + 1000000 출력할 때 숫자 : num - 1000000 이렇게 하면 충분했다.
두 원소의 우선순위가 같다면 원소의 위치를 변경하지 않는다. 사용법은 sort()와 똑같다.
[중요] 비교 함수
sort() 함수의 파라미터로 비교함수를 넘길 수 있다. stable_sort()도 마찬가지다.
예를 들어, int형을 5로 나눈 나머지 순으로, 5로 나눈 나머지가 같다면 크기 순으로 정렬하고 싶으면 아래 코드처럼 하면 된다.
비교함수 cmp는 a가 b의 앞에 와야할 때 true를, 그렇지 않을 때 false를 반환한다.
bool cmp(int a, int b){ // a가 b의 앞에 와야할 때 true, 아니면 false
if(a % 5 != b % 5) return a % 5 < b % 5;
else a < b;
}
int a[7] = {1, 2, 3, 4, 5, 6, 7};
sort(a, a+7, cmp);
// 출력 결과: 5 1 6 2 7 3 4
비교함수 구현 시 자주하는 실수
1. a가 b의 앞에 와야할 때만 true를 반환한다. a==b 라면 false를 반환한다.
예를 들어, 수열을 크기의 내림차순으로 정렬하고 싶을 때, a와 b가 같은 경우 false를 반환하니까 런타임 에러가 발생할 수 있다.
bool cmp(int a, int b){ // [런타임 에러 발생]
if(a >= b) return true;
return false;
}
a > b 일 때 true를 반환하도록 수정하자.
bool cmp(int a, int b){ // 올바른 형태
return a > b;
}
2. 비교 함수의 인자로 STL 혹은 클래스 객체를 전달시 reference를 사용하자.
문자열을 받아서 끝자리의 알파벳 순으로 정렬하고 싶어서 비교함수를 작성했다.
아래의 비교함수는 어떻게 개선하면 좋을까?
bool cmp(string a, string b){
return a.back() < b.back();
}
// 함수의 인자로 STL이나 구조체 객체를 보내면 값의 '복사'가 일어난다!
함수의 인자로 STL이나 구조체 객체를 보내면 값의 '복사'가 일어남을 기억하자!
이 경우, 굳이 복사라는 불필요한 연산이 없어도 비교가 가능하다.
따라서 복사를 하는 대신 아래처럼 reference를 보내는 것이 더 바람직하다.
bool cmp(const string& a, const string& b){ // 레퍼런스를 보내서 비교하는 것이 효율적.
return a.back() < b.back();
}
const string& a, const string& b라고 쓰면 a와 b는 변하지 않음을 명시적으로 나타내기 때문에 가독성이 도움이 된다.
// http://boj.kr/f3feaf22016f4c9687b84ab6be2f4389
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a, a+n);
int cnt = 0;
long long mxval = -(1ll << 62) - 1; // 1을 long long으로 형변환하지 않고 1 << 62로 작성시 int overflow 발생
int mxcnt = 0;
for(int i = 0; i < n; i++){
if(i == 0 || a[i-1] == a[i]) cnt++; // i가 0인 경우 앞쪽 식이 true이기 때문에 a[i-1]을 참조하지 않음
else{
if(cnt > mxcnt){
mxcnt = cnt;
mxval = a[i-1];
}
cnt = 1;
}
}
if(cnt > mxcnt) mxval = a[n-1]; // 제일 마지막 수가 몇 번 등장했는지를 별도로 확인
cout << mxval;
}
코드 마지막 줄에 '제일 마지막 수가 몇 번 등장했는지 별도로 확인'해야 한다.
이 처리가 빠지면 제일 마지막 수의 등장 횟수를 빠뜨리게 된다.
이 문제에서 사용한 정렬을 하면, 같은 수는 인접하게 된다는 성질을 이용해 수열에서 중복된 원소를 제거할 수 도 있다.
#include <bits/stdc++.h>
using namespace std;
int n, num;
int arr[10001];
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++){
cin >> num; arr[num]++;
}
for(int i = 1; i <= 10000; i++){
while(arr[i]){
cout << i << '\n'; arr[i]--;
}
}
return 0;
}
리뷰
이 문제는 sort() 함수를 쓰면 틀린다. 왜냐하면 메모리 제한이 8MB 이다. int 는 4bytes니까. 문제 조건인 천 만개 배열을 선언하면 40MB 를 차지한다. 10000 보다 작은 자연수만 입력으로 들어오니까, 10000을 배열의 인덱스로 두고. 인덱스에 해당하는 숫자의 '개수'를 배열의 값으로 저장해서 해결하면 된다.
그 다음 큰 것을 찾아서 뒤로 보낸다 ... 이렇게 이어질 테니 계산해보면 시간복잡도는 O(N^2) 이다.
선택정렬 코드
int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for(int i = n-1; i > 0; i--){ // 최대값을 찾으면 i위치로 보낼것이다. i:맨 마지막부터 앞에서 두번째 까지.
int mxidx = 0;
for(int j = 1; j <= i; j++){
if(arr[mxidx] < arr[j]) mxidx = j;
}
swap(arr[mxidx], arr[i]);
}
선택 정렬은 가장 큰 수를 찾으면, 인덱스 i로 이동시킨다. 내부 반복문에서 mxidx 인덱스와 j인덱스 자리의 숫자를 비교한다. 이 반복문이 종료되면 가장 큰 숫자의 인덱스가 mxidx에 저장된다. 가장 큰 숫자 인덱스 mxidx와 뒤쪽 인덱스 i를 swap한다. ( == 가장 큰 숫자를 뒤로 보낸다)
max_element 함수로 줄여본 코드
max_element(arr, arr+k)
// arr[0], arr[1], arr[2], .. , arr[k-1] 에서 최댓값인 원소의 주소를 반환
arr[0]부터 arr[k-1] 까지 탐색한 후 최댓값인 원소 주소를 반환한다.
arr[k]가 아니라 arr[k-1]임을 주의하자.
int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for(int i = n-1; i > 0; i--){ // 맨 마지막부터 앞에서 두번째 까지.
swap(*max_element(arr, arr+i+1), arr[i]);
}
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수
// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en){
int mid = (st+en)/2;
int lidx = st; // arr[st:mid]에서 값을 보기 위해 사용하는 index
int ridx = mid; // arr[mid:en]에서 값을 보기 위해 사용하는 index
for(int i = st; i < en; i++){
if(ridx == en) tmp[i] = arr[lidx++];
else if(lidx == mid) tmp[i] = arr[ridx++];
else if(arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
else tmp[i] = arr[ridx++];
}
for(int i = st; i < en; i++) arr[i] = tmp[i]; // tmp에 임시저장해둔 값을 a로 다시 옮김
}
// a[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en){
if(en == st+1) return; // 리스트의 길이가 1인 경우
int mid = (st+en)/2;
merge_sort(st, mid); // arr[st:mid]을 정렬한다.
merge_sort(mid, en); // arr[mid:en]을 정렬한다.
merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
merge_sort(0, n);
for(int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357
}
merge함수에서 두 리스트를 합친 결과를 임시롤 저장할 곳이 필요해서 tmp 변수가 필요하다.
merge_sort함수에서 배열의 크기가 1일 때는 아무것도 안해도 정렬이 완료된다.
이후에는 재귀적으로 절반을 나눠 각각 정렬이 되게 한다.
아직 헷갈리더라도 이건 어려운 내용인것이 맞고 시간과 반복시도가 해결해주는 문제니까 계속 가면 된다.
만약 l 과 r이 타겟을 못찾으면 l > r 이 된다. 인덱스 l과 r이 역전되버린다. 이 때는 break 로 탐색을 멈춘다.
l 과 r이 타겟을 찾으면, swap(arr[l], arr[r]) 스왑 한다!
스왑이 종료되면, 인덱스 r과 인덱스 pivot을 스왑한다.
그리고 pivot을 기준으로 왼쪽과 오른쪽을 보면 pivot이 올바른 자리에 있음을 확인할 수 있다.
나머지 부분은 재귀호출해서 정렬시킨다.
#include <bits/stdc++.h>
using namespace std;
int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
void quick_sort(int st, int en) { // arr[st to en-1]을 정렬할 예정
if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
int pivot = arr[st]; // 제일 앞의 것을 pivot으로 잡는다. 임의의 값을 잡고 arr[st]와 swap해도 상관없음.
int l = st+1; // 포인터 l
int r = en-1; // 포인터 r
while(1){
while(l <= r && arr[l] <= pivot) l++;
while(l <= r && arr[r] >= pivot) r--;
if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
swap(arr[l], arr[r]);
}
swap(arr[st], arr[r]);
quick_sort(st, r);
quick_sort(r+1, en);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
quick_sort(0, n);
for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}
3. 퀵 소트의 시간복잡도
pivot 하나를 올바른 자리에 보낼 때 마다 상수번의 연산으로 l과 r이 한 칸씩 가까워진다.
따라서한 세트의 시간복잡도는 O(N)이다.
재귀 종료 조건인 base condition은 구간의 길이가 1 이하일 때다. pivot을 제자리로 보낸 뒤에, 재귀적으로 자기 자신을 호출한다.
pivot 하나를 올바른 자리에 보내는 세트가 O(N)이 걸리는데.
pivot 을 하나씩 제외하면 N, N-1, N-2 ... 번의 연산이 필요하다.
4. 퀵 소트의 단점?
만약 pivot이 매번 완벽하게 중앙에 위치한다면?
리스트를 균등하게 반으로 쪼개서재귀를 호출하게 된다.
이 때는 n, n/2, n/4 ... 번의 연산이 필요할 것이다. 그러면 머지 소트때와 같이 세트마다 O(logN)이 걸린다.
한 세트의 연산횟수 N과 재귀 호출 연산횟수 logN을 곱하면 된다.
물론 항상 pivot이 완벽하게 중앙에 오지 않겠지만대략 시간복잡도는 O(NlogN)이 된다.
그리고 앞서 말한 cache hit rate가 높아서 퀵 소트는 속도가 굉장히 빠르다.
{1,2,3,4,5,6,7,8} 을 퀵 소트로 정렬하면 시간 복잡도가 얼마일까?
pivot은 항상 중앙에 있는게 아니라. 제일 왼쪽에 위치하게 된다.
그래서 한 단계마다 longN개가 아니라 N개를 확인해야 한다. -> 시간복잡도는 O(N^2)이 된다.
퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이다.
단순히 제일 왼쪽 값을 pivot으로 선택해보면 지금처럼 리스트가 오름차순 이거나 내림차순일 때 O(N^2)이 된다.
[참고]
STL을 못 쓰는 경우, 정렬을 직접 구현해야 한다면 퀵 소트를 쓰는게 아니라 머지 소트를 구현하라고 한 이유가 여기에 있다.
최악의 경우 O(N^2)의 시간복잡도인 퀵 소트를 쓸 필요가 없다.
하지만 대부분의 정렬 라이브러리는 퀵 소트를 쓰는 것도 사실이다.
pivot을 '잘'고르는 것이 관건인데. 랜덤으로 선택하거나. 후보 3개를 정해서 중앙값을 선택하기도 한다.
최악의 경우에도 O(NlogN)을 보장하기 위해 일정 깊이 이상의 재귀가 호출되면 힙 소트로 정렬한다.
재귀가 과도하게 호출되면 오버헤드 때문에 성능저하가 오는 데 이를 피하기 위함이다. 이러한 정렬을 Introspective sort라고 한다.
5. 머지 소트 VS 퀵 소트
머지소트와 퀵 소트는 둘 다 재귀적 구조로 구현된다.
먼저 시간복잡도를 보면 머지소트는 무조건 O(NlogN)이고. 퀵 소트는 최악에 O(N^2), 평균적으로 O(NlogN)이다.
평균적으로 (이름값하는) 퀵 소트가 빠르다.
퀵 소트는 In-Place Sort 인 점을 기억하자.
그리고 머지 소트는 우선 순위가 같은 원소들끼리의 원래 순서가 유지되는 Stable Sort이지만 퀵 소트는 아니다.
