[백준,C++] 1181: 단어 정렬

반응형

728x90

문제

 

---

알파벳 소문자로 이루어진 N개의 단어가 주어졌을 때, 다음과 같은 조건에 따라 정렬하는 프로그램을 작성하십시오.

1. 길이가 짧은 단어부터 정렬합니다.
2. 길이가 같은 경우에는 사전 순으로 정렬합니다.
3. 중복된 단어는 하나만 남기고 제거합니다.

SMALL

입력

 

---

첫째 줄에는 단어의 개수 N이 주어집니다. (1 ≤ N ≤ 20,000) 이후 둘째 줄부터 N개의 줄에 걸쳐 각 줄에는 알파벳 소문자로 이루어진 단어가 하나씩 주어집니다. 주어지는 각 문자열의 길이는 50을 넘지 않습니다.

 

출력

 

---

조건에 따라 정렬하여 단어들을 출력한다.

​

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.

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

bool compareByLength(string a, string b) {
	return  a.length() < b.length();
}

int main() {
	int N;
	vector<string> words;
	cin >> N;
	string temp;
	int i = 0;
	for (i = 0; i < N; i++) {
		cin >> temp;
		words.push_back(temp);
	}

	sort(words.begin(), words.end()); //First sort it Lexicographically
	stable_sort(words.begin(), words.end(), compareByLength); //then by length, but stable_sort to keep previous sort

	cout << words[0] << '\n';
	for (i = 1; i < N;i++) {
		if (words[i] != words[i - 1]) { //since duplicate words are next to each other
			cout << words[i]<< '\n';
		}
		
	}
	cin >> N;
}​

단어들을 입력 받아

길이 순으로 출력

길이 같으면 사전 순으로 출력

같은 단어이면 삭제 하는 조건이라

​

1. 사전순으로 전부 정렬
2. 길이순으로 전부 정렬
3. 그러면 똑같은 단어들은 붙어있기에 이전과 다른 단어들만 출력하면

끝이라고 생각했다

​

하지만

틀렸다고 뜨는 것이다

​

내 코드에서는 예제가 잘 돌아가고

아무리 생각해봐도 틀린게 없는데 왜 맞는데 틀리지 라고 생각했다

​

왜.맞.틀.

​

그러다

​

sort()랑 stable_sort()를 발견했다

​

둘다 sorting 해주는 정렬 함수이다 - <algorithm> library에 들어있음

차이는

​

stable_sort() 순서가 같은 원소들의 상대적 위치를 보존해주는 정렬이다

​

즉

4단어

lame, ill, top, cab

를 stable_sort()를 통해 길이를 오름차순으로 정렬하면

ill, top, cab, lame

순으로 정렬되는 것은 당연하다

하지만 앞에 길이가 같은 3단어들

ill, top, cab

의 순서는 stable_sort()를 사용하지 않고 그냥 sort()를 사용하면 보존되지 않는 것이다

​

나는

사전순 정렬->길이순 정렬을 한 이유가

문제 조건에서 길이가 같은 단어들은 사전순으로 출력해라 했기에

뒤에 사전순으로 정렬한 결과가 유지되어야 한다

​

그래서 stable_sort()를 썼더니

​

<[백준, C++] 2751 : 수 정렬하기2>

 

https://tonnykang.tistory.com/83

[백준, C++] 2751, 수 정렬하기2