글 읽기 - 1181번 단어정렬 질문이요 ㅠ

loveljh 4년 전 0

예제입력이랑 다른것도 입력해도 맞게나오는데 혹시 테스트 케이스 가지고 계신분
조금 주실수 있으신가요?

코드부분은 이렇게 구현했는데 ㅠㅠ 아 몇시간을 찾아도 모르겟네요 ㅠ

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

struct data
{
	string word;
	int length;
};

bool isLower(const data &a, const data &b);
bool isLowerWord(const data &a, const data &b);

int main(){
	
	int n;
	data d[20000];

	//input
	cin >> n;
	for (int i = 0; i < n; ++i){
		cin>>d[i].word;
		d[i].length = d[i].word.length();
	}
		
	sort(&d[0], &d[n], isLowerWord);
	sort(&d[0], &d[n], isLower);

	for (int i = 0; i < n; ++i){
		bool flag = true;

		for (int j = i - 1; j >= 0; --j){
			if (d[i].word == d[j].word){
				flag = false;
				break;
			}
		}
		if (flag) cout << d[i].word << endl;
	}

	return 0; 
}

bool isLower(const data &a, const data &b){
	return a.length < b.length;
}

bool isLowerWord(const data &a, const data &b){
	return a.word < b.word;
}
										

august14 4년 전 1

sort는 stable한 sort가 아니라서 저런식으로 하면 안됩니다.

stable한 sort가 무엇인지는 다음 링크에 잘 설명되어 있습니다. http://entireboy.egloos.com/3516993

stable_sort 함수를 사용하세요

loveljh 4년 전 0

아 그런가요?... 궁금한게 있는데요 stable_sort 나 sort 의 차이점은 알겠습니다.
그래도 저기서는 문자열을 출력해주는거라 딱히 차이없지않나요? 그부분이 좀 궁금합니다.

august14 4년 전 0

그리고 중복된 문자열 처리를 저런식으로 하시면 시간초과가 납니다.

unique함수를 사용하시거나 선형으로 동작하도록 바꾸세요

august14 4년 전 2

처음에 사전순으로 정렬을 한 다음에

길이 순으로 정렬을 하는데, 그때에 길이 순으로 정렬된것들이 순서가 섞여서 문제가 되는겁니다.

loveljh 4년 전 0

아 한번 다시 고쳐보겠습니다 ^^ 감사합니다 궁금한거 또 있으면 댓글남겨도 될까요?

august14 4년 전 0

네 제가 답할수있다면 답해드리겠습니다...

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