목록정렬 (7)
궤도
문제 풀이 예제 입력1을 오름차순 정렬해보자 -10 -9 2 4 4 여기서 중복을 제거하면 -10 -9 2 4 이 배열의 인덱스는 당연히 왼쪽에서부터 0, 1, 2, 3이다. 그리고 이건 각 숫자에 대해 해당 숫자보다 작은 수의 개수가 된다. 소스코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N; long long input; vector arr, sort_arr; cin >> N; for (int i = 0; i > input; arr.push_back(input); //원래 배열 } sort_arr = arr; sort..
문제 풀이 내가 극찬하는 sort 함수는 사실 stable을 보장하지 않는다. 근데 이 문제는 stable sort를 요구한다. 그렇다면 새로 정렬함수를 짜야할까? 그렇지 않다. stable_sort 함수가 있다. 정말 친절하지 않을수가 없다. 이렇게 stable이 보장됐으니, 나이만 고려하면 된다. 소스코드 #include #include using namespace std; struct info { int age; char name[101]; }; bool cmp(const info& p1, const info& p2) { if (p1.age < p2.age) //가입 순이고 stable이면 그냥 나이만 고려하면 됨 return true; else return false; } int main() { ..
문제 풀이 정렬은 어렵지 않다. sort 함수가 있기 때문이다. 먼저 길이 조건으로 한번 걸러주고, 길이가 같은 경우에만 사전 순으로 정렬한다. 사전 순 정렬도 어렵지 않다. string str1, str2가 있을 때 str1이 str2보다 사전 순으로 앞선다면 str1> N; for (i = 0; i > arr[i]; sort(arr, arr + N, cmp); for (i = 0; i < N; i++) { if (arr[i].compare(arr[i + 1]) != 0) //중복 제거 cout
문제 풀이 sort 함수에는 사실 3번째 인자가 있다. 이 3번째 인자를 통해 정렬의 조건을 입맛대로 바꿀 수 있다. 이 인자는 bool을 리턴하는 함수인데, 요구하는 인자의 형식이 중요하다. 그건 아래 코드를 보면 알 수 있다. 사용법도 코드의 주석에 써놓아서 여기에 또 쓸말이 없다. 아무튼 sort 함수는 참 좋다. 소스코드 #include #include using namespace std; struct point { int x, y; }; bool cmp(const point& p1, const point& p2) { //p1이 p2보다 앞에 있어야하는 조건 if (p1.x < p2.x) return true; else if (p1.x == p2.x) return p1.y < p2.y; else ..
문제 풀이 요구하는 것이 많지만, 이 중에서 까다로운건 최빈값 구하기 뿐이다. 입력을 받으면서 모든 배열의 합도 구해놓고, 최댓값과 최솟값도 구해놓는다. 그리고 해당 숫자의 등장 횟수도 count 배열을 갱신하며 기록해준다. 중요한건 입력으로 음수가 들어오기도 한다는 것이다. 범위가 -4,000~4,000 이니까 8,000 크기의 배열을 선언하고 입력으로 들어온 값에 4,000을 더한 인덱스를 갱신하면 된다. -4,000~4,000의 범위가 0~8,000으로 변하는 셈이다. 입력을 다 받았으면 중앙값을 구하기 위해 정렬한다. 그리고 count 배열을 돌며 최빈값을 체크한다. 해당 최빈값이 유일하다면 바로 출력하면 되지만, 유일하지 않다면 배열을 다시 돌며 최빈값 중 두 번째로 작은 값을 출력한다. 최빈값..
문제 풀이 이 문제 굉장히 힘들었다. 문제 힌트에 counting sort를 사용하라고 써있어서 정석적인 counting sort로 구현했다. counting sort(계수 정렬)이 어떤 것인지 설명하는 곳은 굉장히 많으므로 생략하도록 하겠다. 아무튼 계수 정렬을 구현하려면 배열이 3개 필요하다 정렬 전 배열, 배열의 값의 누적합을 저장한 배열, 정렬 후 배열. 열심히 구현하고 채점을 돌린 나는 메모리 초과를 맞이했다. N크기의 배열을 동적할당하는 과정에서 메모리 초과가 발생한 것일까? 그래서 처음부터 max만큼의 고정 배열을 선언했다. 또 메모리 초과였다. 찾아보니 정렬 전 배열과 정렬 후 배열을 만들면 안된다고 한다. 정렬 전 배열조차 저장하지 말라니? 아무래도 이 문제는 내가 생각한 계수 정렬이 아..
문제 문제 이 문제에서 처음으로 C++에 내장된 정렬함수인 sort를 사용해봤다. 그리고 난 이제 그 이전으로 돌아갈 수 없다. sort 함수는 구조체도 정렬하고 문자열도 정렬하고 오름차순, 내림차순 그냥 내가 적당히 조건을 넣으면 다 정렬해준다. 이 함수의 활용도에 대해 말할 수 있는 기회는 뒤로도 충분히 많으니 일단 간단한 사용법만 소개한다. sort 함수는 기본적으로 오름차순 정렬을 한다. 정렬하고자 하는 배열이 있을 때 그 배열의 첫 인덱스와 마지막 인덱스+1 을 인자로 넣어주면 바로 정렬할 수 있다. 이 말은 즉, 내가 넣는 인덱스에 따라서 배열 전체가 아니라 배열의 일부만 정렬할 수도 있다는 것이다. 소스코드 #include #include using namespace std; int main..