[백준 Class 2] 1181번 단어 정렬 C++ 풀이

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

문제 링크입니다.

 

이 문제의 난이도는 실버5로 문자열과 정렬을 능숙하게 사용할 줄 아는지 묻는 문제입니다.

중복을 허용하지 않는다라고 생각해서 set 자료구조를 떠올리셨을 수도 있겠지만, 굳이 그럴 필요는 없습니다.

1. 길이가 짧은 것 부터

2. 길이가 같으면 사전 순으로

문제에서 제시된 정렬 조건에 맞게 구현하시면 됩니다.

저 같은 경우는 algorithm 헤더에 있는 sort 함수를 사용했습니다.

마지막 인자로 사용자가 정의한 cmp 함수로 문제에서 제시된 조건을 구현했습니다.

단지 조심해야 될 조건은 중복 제거입니다.

입력받음과 동시에 중복을 제거하는 경우가 아니라, 정렬을 먼저 하고 중복을 제거하실 수도 있는데요

이 때, 중복 제거를 신경써주시지 않으면 (Ex. Linear하게 제거하는 경우) 5개의 단어를 입력받았을 때, a a a a a 의 입력이 들어올 경우, 정확히 하나의 a를 리턴하지 않을 가능성이 매우 큽니다.

따라서 중복 제거를 먼저 하시는 것을 추천드립니다 :)

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


bool cmp(string x, string y) {
	if (x.length() == y.length())
		return x < y;
	return x.length() < y.length();
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin >> N;
	vector<string> orig;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		if (find(orig.begin(), orig.end(), s) == orig.end())
			orig.push_back(s);
	}
	sort(orig.begin(), orig.end(), cmp);
	for (int i = 0; i < orig.size(); i++) {
		cout << orig[i] << '\n';
	}
}