문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

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

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력/출력

코드

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

using namespace std;

int main() {
	int n;
	string str;
	vector<string> ans;
	vector<string>::iterator s;

	scanf("%d", &n);

	cin >> str;
	ans.push_back(str);
	n--; 

	while (n--) {
		int skip = 0;

		cin >> str;

		for (s = ans.begin(); s < ans.end(); s++) { 
			if (str.compare(*s) == 0) // 중복으로 입력받은 문자열 무시
				skip = 1;
			else if (str.length() < (*s).length()) // str이 vector의 s위치의 문자열보다 길이가 작음
				break;
			else if (str.length() == (*s).length()) {
				if (str.compare(*s) < 0) // str이 사전순으로 앞일 때
					break;
			}
		}

		if(!skip)
			ans.insert(s, str);
	}

	for (vector<string>::iterator i = ans.begin(); i < ans.end(); i++)
		cout << *i << '\n';

	return 0;
}

풀이

이번 문제는 string을 잘 쓰면 쉽게 풀린다.
비교의 우선순위를 확인하자면 길이(짧은순) -> 사전순(오름차순) 이다.
따라서

1. 문자열의 길이를 비교하고( length()함수 사용 )
2. 길이가 같다면 사전순( compare()함수 사용 )으로 비교하여
3. 원하는 index에 입력받은 str을 vector에 저장한다.