글 읽기 - 귀중한 시간 잠시 내어주시면 감사하겠습니다..

kwak2418 2년 전 1

안녕하세요 여러분 병합정렬을 드디어 어느 정도 이해하고 혼자 짜봤는데요

정렬은 잘되는데 이론 상 stableSort가 되야 하는데 입력을 여러번 해보니 안되는 구간이 있더라구요..

하루종일 뒤져봐도 어디 쪽에서 stable 속성이 안들어 갔는지 모르겠어요 ㅜㅜ

지적 좀 해주세요

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

#define endl "\n"
#define INF 987654321
using namespace std;

void merge(vector<pair<int,string>> &v,int start,int mid,int end)
{
	vector<pair<int,string>> temp=vector<pair<int,string>>(v.size());


	
	int left_idx=start;
	int right_idx=mid+1;
	int k=start;
	while(left_idx<=mid&&right_idx<=end)
		{
			// 같을 경우 왼쪽 우선(stable sort)
			if(v[left_idx]<=v[right_idx])
			{
				temp[k]=v[left_idx];
				left_idx++;
			}
			else
			{
				temp[k]=v[right_idx];
				right_idx++;
			}
			k++;
		}
	 
	/*
        left_idx 가 mid를 넘었다는 뜻은 left쪽은 전부 체크 했다는 뜻 , 즉 오른쪽 부분에 남아있으므로
        남아있는 것 시작 entry는 right_idx가 되고
        target역시 end가 된다
        만약 left_idx가 mid를 넘지 않았다면, 왼쪽에 남아 있는게 있다는 뜻
    */

	int entry = (left_idx > mid) ? right_idx:left_idx;
	int target= (left_idx > mid) ? end : mid;
	//남아 있는 값들 복사 
	for (int t = entry; t <= target; ++t)
	{
		temp[k] = v[t];
		k++;
	}
	//정렬된 임시 리스트를  원래 리스트에 복사 
	for (int t = start; t <= end; ++t)
	{
		v[t] =temp[t];
	}
	
	
	
}

void mergeSort(vector<pair<int, string> > &v, int p, int r)
{

	if(p<r)
	{
		int q=(p+r)/2; //중간 값(물리적 중간 값) 찾기 (중간 값은 왼쪽의 끝값) ,오른쪽의  start값으로 사용(q+1)
		mergeSort(v,p,q); //왼쪽 
		mergeSort(v,q+1,r); //오른쪽 
		merge(v,p,q,r); // 병합
	}
}

int main(void)
{
    int n;
    vector<pair<int, string> > v;
	
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int d;
        string s;
        cin >> d >> s;
        v.push_back(pair<int, string>(d, s));
    }

    // mergeSort sort
    mergeSort(v, 0, v.size()-1);

    // output
   
    for (int i = 0; i < n; i++)
    {
        cout << v[i].first << ' ' << v[i].second << endl;
    }

    return 0;
}

pichulia 2년 전 1

21번째 줄을 보시면 pair<int, string> 단위로 비교연산을 하고 있는데 이것이 의도랑 맞는 동작인지 확인해보세요.

"stable"인지 아닌지 확인한다는 의미는 비교연산자 상으로 !(a<b || b<a ) 를 만족하는 서로 다른 두 a,b 가 있다는 의미인데

pair<int, string> 은 서로 다른 두 값은 항상 a<b || b<a 를 만족하므로

stable 성질을 전혀 써먹을 구석이 없습니다.

다음과 같은 입력에 대해서

0 b

0 a

가 나와야 하는지

0 a

0 b

가 나와야 하는지부터 확인해보시길 바랍니다.

그리고 여담인데, temp 배열의 크기를 너무 크게 잡고 있습니다. 현재와 같은 구현방식으로는 temp 배열 메모리 할당으로 인해 시간복잡도가 O(n^2) 이 나옵니다. 이 부분은 수정이 필요합니다.

2
0 b
0 a

kwak2418 2년 전 0

정말 자세하고 깔끔한 설명 감사드립니다.

여담으로 해주신 temp 메모리 할당 관련하여 추가 질문 드립니다.

end-start로 해주면 적절할 까요?

pichulia 2년 전 0

네. 정확히는 temp = vector<~~>(end-start+1); 만큼의 메모리가 필요할겁니다.

kwak2418 2년 전 0

end-start ~ end-start+2 까지 해봤는데요ㅜㅜ 계속해서 segement falut가 검출 됩니다..

kwak2418 2년 전 0

18 번째 k의 시작과 51번 째 마지막 처리의 index를 잘 맞춰주니 동작 너무 잘됩니다 정말 감사합니다 ^^

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

#define endl "\n"
#define INF 987654321
using namespace std;

void merge(vector<pair<int,string>> &v,int start,int mid,int end)
{
	cout <<(end-start+1) <<endl;
	vector<pair<int,string>> temp=vector<pair<int,string>>(end-start+1);


	
	int left_idx=start;
	int right_idx=mid+1;
	int k=0;// temp 접근 시 시작, temp와 vector의 크기가 다르기 때문에 
	while(left_idx<=mid&&right_idx<=end)
		{
			// 같을 경우 왼쪽 우선(stable sort)
			if(v[left_idx].first<=v[right_idx].first)
			{
				temp[k]=v[left_idx];
				left_idx++;
			}
			else
			{
				temp[k]=v[right_idx];
				right_idx++;
			}
			k++;
		}
	 
	/*
        left_idx 가 mid를 넘었다는 뜻은 left쪽은 전부 체크 했다는 뜻 , 즉 오른쪽 부분에 남아있으므로
        남아있는 것 시작 entry는 right_idx가 되고
        target역시 end가 된다
        만약 left_idx가 mid를 넘지 않았다면, 왼쪽에 남아 있는게 있다는 뜻
    */

	int entry = (left_idx > mid) ? right_idx:left_idx;
	int target= (left_idx > mid) ? end : mid;
	//남아 있는 값들 복사 
	for (int t = entry; t <= target; ++t)
	{
		temp[k] = v[t];
		k++;
	}
	//정렬된 임시 리스트를  원래 리스트에 복사
	int p=0; //temp 접근 시 시작
	for (int t = start; t <= end; ++t)
	{
		v[t] =temp[p++];
	}
	
	
	
}

void mergeSort(vector<pair<int, string> > &v, int p, int r)
{

	if(p<r)
	{
		int q=(p+r)/2; //중간 값(물리적 중간 값) 찾기 (중간 값은 왼쪽의 끝값) ,오른쪽의  start값으로 사용(q+1)
		mergeSort(v,p,q); //왼쪽 
		mergeSort(v,q+1,r); //오른쪽 
		merge(v,p,q,r); // 병합
	}
}

int main(void)
{
    int n;
    vector<pair<int, string> > v;
	
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int d;
        string s;
        cin >> d >> s;
        v.push_back(pair<int, string>(d, s));
    }

    // mergeSort sort
    mergeSort(v, 0, v.size()-1);

    // output
   
    for (int i = 0; i < n; i++)
    {
        cout << v[i].first << ' ' << v[i].second << endl;
    }

    return 0;
}

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

문제

문제

출처

ICPC

귀중한 시간 잠시 내어주시면 감사하겠습니다..

kwak2418 2년 전 1

pichulia 2년 전 1

kwak2418 2년 전 0

pichulia 2년 전 0

kwak2418 2년 전 0

kwak2418 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말