1181 - 단어 정렬

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

1181번: 단어 정렬

0. 개요

 

이번 문제의 조건은 다음과 같습니다.

1. 길이가 짧은 것 부터

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

3. 여러번 입력된 단어는 한 번만 출력한다

 

길이가 같으면 사전순으로 정렬하는 것은 sort 함수가 처리 해 줄테니 1, 3번만 고려하면 되겠습니다.

 

1. 소스 코드

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

bool compare(string a, string b) {
	if (a.length() == b.length()) return a < b;
	else return a.length() < b.length();
}

int main(void) {
	string arr[200000];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n, compare);

	for (int i = 0; i < n; i++){
		cout << arr[i] << "\n";
		while (!arr[i].compare(arr[i + 1])) 
			i++;
		
	}
	return 0;
}

 

1. compare 함수를 통하여 길이가 짧은 순으로, 길이가 같으면 사전순으로 먼저 정렬해줍니다.

2. 중복되는 문자열의 경우 다음번의 문자열과 비교하여 같다면 반복에 사용되는 변수 i를 1 증가하므로써 건너뛰는 효과를 주어 해결했습니다.

 

2. 마무리

정렬과 같이 저명한 파트는 이미 구현된 훌륭한 알고리즘이 너무 많습니다.

따라서 문제 풀이 시간도 자연스럽게 줄어들었습니다.