글 읽기 - [C++] 모르겠어요...

alsrb0504 4년 전 0

구조체 배열과 퀵 솔트를 이용해서 풀었습니다.

예제는 정답에 맞게 나오는데, 어디서 틀린 건지 모르겠네요...

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

//void swap(int* a, int* b);
int partition(int left, int right, struct human *p);
void quickSort(int left, int right, struct human *p);
void swap(struct human *a, struct human *b);

struct human {
	int number;
	int age;
	string name;
};

struct human p[100000];

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

	for (int i = 0; i < n; i++) {
		p[i].number = i;
		cin >> p[i].age;
		cin >> p[i].name;
	}
	// 퀵 솔트로 일단 정렬.
	quickSort(0, n - 1, p);

	// 나이가 같으면, 등록 순으로 정렬
	for (int i = 0; i < n-1; i++) {
		if (p[i].age == p[i + 1].age)
		{
			if (p[i].number > p[i + 1].number)
			{
				swap(&p[i], &p[i + 1]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		cout << p[i].age << " ";
		cout << p[i].name << "\n";
	}

	return 0;
}

void swap(struct human *a, struct human *b) {
	struct human imsi;
	imsi = *a;
	*a = *b;
	*b = imsi;
}

int partition(int left, int right, struct human *p) {
	//가장 오른쪽 거를 pivot으로 설정.
	int pivot = p[right].age;
	int i = left - 1;

	for (int j = left; j <= right - 1; j++) {
		if (p[j].age <= pivot)
		{
			i++;
			swap(&p[i], &p[j]);

		}
	}
	// 마지막에 피봇의 위치를 바꿔줌.
	//swap(&p[i + 1].age, &p[right].age);
	swap(&p[i + 1], &p[right]);
	// 피봇의 위치 리턴.
	return (i + 1);
}

void quickSort(int left, int right, struct human *p) {
	if (left < right)
	{
		int pivot = partition(left, right, p);

		quickSort(left, pivot - 1, p);
		quickSort(pivot + 1, right, p);
	}
}

bupjae 4년 전 0

30번~39번 줄에서 작성한 알고리즘은 불완전합니다. bubble sort 를 딱 한 번만 돌린 꼴입니다.

정렬 조건이 여러 가지인 데이터를 정렬할 때에는 정렬 내부에서 사용하는 비교문 (여기서는 61번째 줄)을 작성할 때 모든 경우의 수를 따져야 합니다.

한 가지 정렬 조건으로만 먼저 정렬한 뒤 나중에 다른 정렬 조건으로 정렬하는 방식으로 작성하려면 신경써야 할 것이 매우 많으며 실수하기도 쉽습니다.

입력:
5
A
B
C
D
E


정답:
E
A
B
D
C


오답:
E
B
A
D
C

alsrb0504 4년 전 0

감사합니다.

덕분에 해결했습니다. ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 모르겠어요...

alsrb0504 4년 전 0

bupjae 4년 전 0

alsrb0504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말